递归实现Combination Sum代码失效，求错误原因及修正思路

问题背景 #

我是数据结构新手，正在解决LeetCode的Combination Sum问题，目前学习递归，希望找出代码错误以纠正思路。题目要求如下：

给定由不同整数组成的candidates数组和目标值target，返回所有和为target的唯一组合，同一数字可重复选取，组合唯一判定标准为至少一个数字的频率不同。测试用例保证符合条件的组合数少于150种。

我编写了如下JavaScript代码，当前目标是实现组合（暂不考虑去重），但代码无法正常运行，无法理解原因：

var combinationSum = function(candidates, target) {
    if(candidates.length == 0) return [[]]
    if(target == 0) return [[]]
    if(target<0) return []
    result = []
    for(let i=0; i<candidates.length; i++){
        let arr = [...candidates]
        // take the element
        let result1 = combinationSum([...candidates], target-candidates[i])
        // ignore the element
        result1.forEach((e)=>{e.push(candidates[i])})
        let result2 = combinationSum(arr.slice(0, i).concat(arr.slice(i + 1)), target)
        result.push(...result1, ...result2)
    }
    return result
};

代码错误分析 #

• 全局变量污染：result = []未用let/const声明，会成为全局变量，递归过程中被多次修改，导致结果混乱。
• 递归逻辑重复冗余：循环遍历所有元素时，同时执行“选当前元素”和“不选当前元素”分支，且选元素时传入完整candidates数组，会导致无限递归或大量重复计算，组合逻辑完全混乱。
• 边界条件错误：candidates.length == 0时返回[[]]不合理，此时无元素可选，无法组成非0的target，应返回[]。
• 数组引用副作用：result1.forEach((e)=>{e.push(candidates[i])})直接修改递归返回的数组元素，因数组是引用类型，会污染递归过程中的其他结果。

修正思路与代码 #

Combination Sum允许重复选同一元素，正确的递归核心是按顺序选择，通过起始索引避免重复组合：

• 递归参数增加起始索引，确保选完当前元素后，后续只从当前索引及之后的元素选择，既允许重复选当前元素，又避免生成重复组合。
• 当剩余目标值为0时，复制当前路径存入结果；剩余值小于0时直接终止递归。
• 用回溯逻辑处理“选/不选”分支：选当前元素后递归，回溯时移除元素再尝试不选的情况。

修正后的代码：

var combinationSum = function(candidates, target) {
    const result = [];
    
    const backtrack = (start, currentPath, remaining) => {
        if (remaining === 0) {
            result.push([...currentPath]);
            return;
        }
        if (remaining < 0) {
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            currentPath.push(candidates[i]);
            // 允许重复选当前元素，所以起始索引保持i不变
            backtrack(i, currentPath, remaining - candidates[i]);
            // 回溯，移除当前元素
            currentPath.pop();
        }
    };
    
    backtrack(0, [], target);
    return result;
};

关键说明 #

• 用回溯法实现递归，通过起始索引控制选择范围，自然避免重复组合。
• 每次记录结果时复制当前路径（[...currentPath]），避免引用类型的修改副作用。
• 边界条件清晰：剩余目标值为0时记录有效组合，小于0时终止无效分支。

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