組合總和蟒蛇遞歸範圍

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)