递归生成和为n的数组元素组合：C程序输出不符预期求助

原代码核心问题分析 #

原代码无法正确生成所有符合要求的组合，主要存在以下问题：

• 未限制元素范围：循环遍历了整个20个元素的数组，包含5及以上的无效元素，导致大量无意义的递归调用。
• 缺少组合路径跟踪：没有记录递归过程中选择的元素，无法完整输出每个有效组合的序列。
• 递归终止逻辑错误：仅在n<1时直接返回，未处理n=0（即找到有效组合）的情况，无法触发完整组合的打印。
• 打印逻辑缺陷：仅当n等于某个元素时才打印单个值，无法累积组合中的元素序列。

修正后的代码 #

#include <stdio.h>

// 递归函数：n为剩余目标和，values为可用元素数组，path记录当前组合，path_len为当前组合长度
void findCombinations(int n, int values[], int path[], int path_len) {
    // 终止条件：剩余和为0，输出当前组合
    if (n == 0) {
        for (int i = 0; i < path_len; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
        return;
    }
    // 剩余和小于0，直接返回（无效路径）
    if (n < 0) {
        return;
    }
    
    // 仅遍历前4个元素（1、2、3、4，符合小于5的要求）
    for (int i = 0; i < 4; i++) {
        // 将当前元素加入组合路径
        path[path_len] = values[i];
        // 递归调用：剩余和减去当前元素，组合长度+1
        findCombinations(n - values[i], values, path, path_len + 1);
    }
}

int main() {
    int values[] = {1,2,3,4,5,6,7,9,10,20,30,40,50,60,70,80,100,200,300,600}; 
    int n;
    // 定义路径数组，最大长度设为n（最坏情况全选1）
    int path[100];
    
    scanf("%d", &n);
    findCombinations(n, values, path, 0);
    return 0 ;
}

代码说明 #

1. 路径跟踪机制：新增path数组和path_len参数，实时记录递归过程中选择的元素，当n=0时遍历路径数组打印完整组合。
2. 元素范围控制：循环仅遍历前4个元素，确保只使用1、2、3、4这四个符合要求的元素。
3. 修正终止逻辑：n=0时输出组合，n<0时直接返回，避免无效递归分支。
4. 递归回溯优化：由于path_len是值传递，递归返回后下一次循环会自动覆盖当前位置的元素，无需额外的回溯操作。

测试输入n=3时，输出如下：

1 1 1 
1 2 
2 1 
3 

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