组合总和蟒蛇递归范围

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

看起来像一个参考问题。尝试：

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

这将创建path浅拷贝，因此在后面的代码上进行path任何pop将里面res列表上的没有影响。

Answer 2

行

res.append(path) 

更改为

res.append(path[:]) 

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

path.pop(len(path)-1)