组合和python递归scop

Question

我实现了一个组合求和算法来解决以下问题：

# Given an array: [10,1,2,7,6,1,5]
# and a target: 8
# Find the solution set that adds up to the target
# in this case:
# [1, 7]
# [1, 2, 5]
# [2, 6]
# [1, 1, 6]

def cominbationSum(arr, target):
    arr =sorted(arr)
    res = []
    path = []
    dfs_com(arr, 0, target, path, res)
    return res

def dfs_com(arr, curr, target, path, res):
    if target == 0:
        res.append(path)
        return
    if target < 0:
        return
    for i in range(curr, len(arr)):
        if i > curr and arr[i] == arr[i-1]: # skip duplicates
            continue
        path.append(arr[i])
        dfs_com(arr, i+1, target - arr[i], path, res)
        path.pop(len(path)-1)


print cominbationSum([10,1,2,7,6,1,5], 8)

我的算法生成正确的组合，但在返回res时遇到问题。它将res返回为[[],[],[],[]]，而不是[[1, 1, 6],[1, 2, 5],[1, 7],[2, 6]]。知道路径为什么不能正确地附加到res上吗？在

Answer 1

换行

res.append(path)

到

^{pr2}$

所以你得到的是路径的副本而不是路径本身。问题是因为您要删除行中的元素：

path.pop(len(path)-1)

Answer 2

看来是个参考问题。尝试：

if target == 0:
    res.append(path[:])
    return

这将创建path的一个浅拷贝，因此在代码中稍后对path执行的任何pop都不会对{}内的列表产生任何影响。在