Combination Sum递归回溯代码无输出问题排查求助

核心错误：终止条件逻辑错误 #

原代码的终止判断要求tempSum == target必须同时满足i == len(arr)，但实际上绝大多数合法组合根本不需要遍历完整个数组就能凑出target。比如组合[3,3]，当我们在索引2（元素3）重复选取两次时，tempSum已经等于6，但此时i并没有到达数组长度（len(arr)=3，i=2），这个条件直接把所有合法组合都排除了，导致无输出。

修正后的终止条件 #

只要tempSum == target就输出结果，无需等待遍历完数组；当tempSum > target或i == len(arr)时直接返回即可。

完整修正代码 #

def combinationSum(arr, i, target, tempSum, tempList):
    # 找到合法组合，直接输出
    if tempSum == target:
        print(tempList)
        return
    # 超出数组边界或和超过target，终止递归
    if i == len(arr) or tempSum > target:
        return

    # 情况1：不选当前元素，跳至下一个元素
    combinationSum(arr, i+1, target, tempSum, tempList.copy())

    # 情况2：选取当前元素，继续留在当前索引（支持重复选取）
    tempSum += arr[i]
    tempList.append(arr[i])
    combinationSum(arr, i, target, tempSum, tempList.copy())

combinationSum([1, 2, 3], 0, 6, 0, [])

补充说明 #

原代码中通过tempList.copy()传递列表副本的方式是合理的，属于“显式复制”的回溯思路，无需手动回溯pop操作，问题完全出在终止条件的逻辑判断上。

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