LeetCode组合总和问题：两种递归实现为何一成功一失败？

问题背景 #

给定由不同整数组成的数组candidates和目标整数target，返回所有候选数的唯一组合列表，使所选数字之和等于target，组合顺序不限。同一候选数可被无限次选取，只要至少一个数字的出现频率不同，组合即视为唯一。测试用例保证符合条件的组合数少于150个。
示例1：输入candidates = [2,3,6,7], target = 7，输出[[2,2,3],[7]]

第一种通过的代码 #

def help(self, i, s, c, t, arr, ans):
    if s == t:
        ans.append(arr)
        return
    if i == len(c) or s > t:
        return
    self.help(i+1, s, c, t, arr, ans)
    self.help(i, s+c[i], c, t, arr + [c[i]], ans)

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    self.help(0, 0, candidates, target, [], ans)
    return ans

第二种失败的回溯写法 #

def help(self, i, s, c, t, arr, ans):
    if s == t:
        ans.append(arr)
        return
    if i == len(c) or s > t:
        return
    self.help(i+1, s, c, t, arr, ans)
    arr.append(c[i])
    self.help(i, s+c[i], c, t, arr, ans)
    arr.pop()

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    self.help(0, 0, candidates, target, [], ans)
    return ans

核心差异：列表引用 vs 新列表副本 #

第一种写法中，arr + [c[i]]是创建一个全新的列表，递归传递的是这个新列表的副本。当递归触发s == t时，ans.append(arr)添加的是当前状态的独立列表，后续递归的回溯操作不会修改它。

第二种写法用append+pop做回溯时，传递的是原列表的引用。当s == t时，你把arr的引用存入ans，但后续的pop()会修改原列表的内容——因为ans里存的是引用而非副本，最终ans中的列表会被回溯操作改得面目全非（比如变成空列表），导致输出错误。

修复第二种写法的方法 #

只需要在找到符合条件的组合时，添加arr的副本到ans，而不是原引用：

if s == t:
    ans.append(arr.copy())  # 等价于 ans.append(list(arr))
    return

这样即使后续arr被回溯修改，ans中存储的是当时状态的独立副本，不会被影响。

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