递归生成指定和的数字组合：C语言代码异常求助

问题背景 #

给定数字数组[2,6]，目标和为10，需输出所有满足和为10的数字组合，预期输出：

2,2,2,2,2
6,2,2
2,6,2
2,2,6

当前代码仅输出2,2,2,2,2，还会出现异常大负数，需排查问题。

用户当前代码 #

#include <stdio.h>
#include <stdlib.h>

typedef struct val_s {
    int num_choice;
    int *choices;
} val_t;

int sum(int *sol,int pos,int n) {
    int s=0;
    for (int i = 0; i < pos; ++i) {
        s=s+sol[i];
    }
    if(s==n)
        return 1;

    return 0;

}

void mult_princ(val_t *val,int *sol, int n, int pos)
{

    if(sum(sol,pos,n))
    {
        for (int i = 0;  i< pos; i++) {
            printf("%d ",sol[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 0; i < val[i].num_choice; ++i) {
        sol[pos]=val[pos].choices[i];
        mult_princ(val,sol,n,pos+1);
    }
    return;
}
int main() {

    int *sol;
    val_t *val;
    int n=10;
    val = malloc(n*sizeof(val_t));
    if (val == NULL) {
        exit(1);
    }

    for (int i = 0; i < n; ++i) {
        val[i].num_choice=2;
        val[i].choices = malloc(val[i].num_choice * sizeof(int));
        if (val[i].choices == NULL) {
            exit(1);
        }
        val[i].choices[0] = 2;
        val[i].choices[1] = 6;

    }
    sol = malloc(n * sizeof(int));
    if (sol == NULL)
    {
        exit(1);
    }
    mult_princ(val,sol,n,0);

    return 0;
}

问题分析与修复 #

1. 循环变量与数组索引冲突 #

递归函数mult_princ中的循环条件存在致命错误：

for (int i = 0; i < val[i].num_choice; ++i)

循环变量i被同时用作val数组的索引，递归过程中会出现越界访问，读取非法内存值（表现为大负数）。需将循环变量改为独立名称（如j），并使用当前递归层级pos的选项数：

for (int j = 0; j < val[pos].num_choice; ++j)

2. 缺少剪枝逻辑 #

当前代码未判断当前和是否超过目标值，会进行大量无效递归，甚至导致数组越界。需修改求和逻辑，返回当前和的状态：

• 返回1：和等于目标值
• 返回0：和小于目标值
• 返回2：和大于目标值

递归时若当前和已超过目标值，直接终止递归，避免无效计算。

3. 递归终止条件完善 #

在递归前先判断当前和的状态，若已超过目标则直接返回，无需继续添加数字。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>

typedef struct val_s {
    int num_choice;
    int *choices;
} val_t;

// 返回当前和的状态：1=等于目标，0=小于，2=大于
int get_sum_status(int *sol, int pos, int target) {
    int s = 0;
    for (int i = 0; i < pos; ++i) {
        s += sol[i];
    }
    if (s == target) return 1;
    return s < target ? 0 : 2;
}

void mult_princ(val_t *val, int *sol, int target, int pos)
{
    int status = get_sum_status(sol, pos, target);
    if (status == 1) {
        // 按预期格式打印结果
        for (int i = 0; i < pos; ++i) {
            if (i > 0) printf(",");
            printf("%d", sol[i]);
        }
        printf("\n");
        return;
    }
    if (status == 2) {
        // 和已超过目标，终止递归
        return;
    }

    // 遍历当前位置的所有可选数字
    for (int j = 0; j < val[pos].num_choice; ++j) {
        sol[pos] = val[pos].choices[j];
        mult_princ(val, sol, target, pos + 1);
    }
}

int main() {
    int *sol;
    val_t *val;
    int target = 10;
    // 最多需要target/2个数字（全选2的情况），优化内存分配
    int max_len = target / 2;
    val = malloc(max_len * sizeof(val_t));
    if (val == NULL) {
        exit(1);
    }

    for (int i = 0; i < max_len; ++i) {
        val[i].num_choice = 2;
        val[i].choices = malloc(val[i].num_choice * sizeof(int));
        if (val[i].choices == NULL) {
            exit(1);
        }
        val[i].choices[0] = 2;
        val[i].choices[1] = 6;
    }
    sol = malloc(max_len * sizeof(int));
    if (sol == NULL) {
        exit(1);
    }

    mult_princ(val, sol, target, 0);

    // 释放内存，完善内存管理
    for (int i = 0; i < max_len; ++i) {
        free(val[i].choices);
    }
    free(val);
    free(sol);

    return 0;
}

修复后的输出 #

运行后将得到符合要求的结果（包含所有合法顺序的组合）：

2,2,2,2,2
2,2,2,6
2,2,6,2
2,6,2,2
6,2,2,2

内容的提问来源于stack exchange，提问作者Severjan Lici