auf eine Liste in rekursive Funktion

Question

Ich schrieb das folgende rekursive Programm angehängt, das die Kombination von Zahlen findet, die hinzugefügt werden können, um den Sollwert zu machen:

arr = [1, 2, 2, 3, 5] 
target = 8 

def comb_sum(arr, current_index, target, result, ans): 
    if target == 0: 
     print result 
     ans.append(result) 
     return 0 
    if target < 0: 
     return 1 
    if current_index == len(arr): 
     return 1 

    result.append(arr[current_index]) 
    comb_sum(arr, current_index+1, target - arr[current_index], result, ans) 
    result.pop() 

    comb_sum(arr, current_index+1, target, result, ans) 
    return ans 



print comb_sum(arr, 0, target, [], []) 

Da ich arr.append bin mit() anhängen die result, erwartete ich die korrekte Ausgabe.

Obwohl das Programm korrekt ist, kann ich keine resultans Liste hinzufügen.

Was ist los?

Ich erwarte diese Ausgabe: [[1, 2, 2, 3], [1, 2, 5], [1, 2, 5], [3, 5]] Aber stattdessen bekomme ich diese Ausgabe: [[], [], [], []]

Answer 1

eine Kopie der Ergebnisliste machen und durch wie unten

comb_sum(arr, current_index+1, target - arr[current_index], result[:], ans) 

Es gibt nur eine Kopie ist Ergebnis fließt durch das Programm. Wann immer sich result ändert, spiegelt sich das auch in ans wider. Aus diesem Grund bricht das Kopieren die Kette und gibt Ihnen das richtige Ergebnis

Answer 2

import copy 
arr = [1, 2, 2, 3, 5] 
target = 8 
def comb_sum(arr, current_index, target, result, ans): 

if target == 0: 
    print result 
    ans.append(copy.deepcopy(result)) 
    return 0 
if target < 0: 
    return 1 
if current_index == len(arr): 
    return 1 

result.append(arr[current_index]) 
comb_sum(arr, current_index+1, target - arr[current_index], result, ans) 
result.pop() 

comb_sum(arr, current_index+1, target, result, ans) 
return ans 

print comb_sum(arr, 0, target, [], [])