为什么我写的Python递归解法无法正确求解LeetCode Combination Sum问题

核心问题 #

你遇到的是Python可变对象的引用传递特性导致的问题，全程复用同一个列表实例追加到结果集，后续回溯操作会修改已存入的列表内容。

两个写法的差异对比 #

• 正常运行的写法：
  递归调用时使用numbers+[candidates[i]]传参，该操作会生成全新的独立列表实例，每个符合条件被存入result的列表都不会被后续操作修改，因此结果正常。
• 你的写法：
  全程操作同一个subset列表实例，执行res.append(subset)时仅存入了该列表的引用，后续递归返回后的subset.pop()操作会持续修改这个列表的内容，整个回溯流程结束后，所有存入res的引用指向的同一个列表已经被清空，所以你得到的全是空列表。

另外你代码里写的subset = []是无效操作，只是给函数内的局部变量重新赋值，不会修改实际传入的列表实例，可以直接删除。

修复方案 #

仅需要在追加结果时存储当前列表的副本即可，修改res.append(subset)为以下任意一种写法：

# 写法1
res.append(subset.copy())
# 写法2
res.append(list(subset))
# 写法3
res.append(subset[:])

修复后的完整代码：

def combinationSumMine(candidates, target):
    res = []
    def findCombos(subset):
        current_sum = sum(subset)
        if current_sum > target:
            return
        if current_sum == target:
            res.append(subset.copy())
            return
        for i in range(len(candidates)):
            subset.append(candidates[i])
            findCombos(subset)
            subset.pop()
    findCombos([])
    return res

运行后即可得到和正常写法一致的结果。

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