顯示子集子集和

Question

我有以下的算法，遞歸解決子集和問題：

def findSubset(alist, targ, i, sumsofar): 
    if sumsofar == targ: 
     return True 
    if i == len(alist): 
     return False 
    inc = findSubset(alist, targ, i+1, sumsofar+alist[i]) 
    noninc = findSubset(alist, targ, i+1, sumsofar) 
    return inc or noninc 

算法工作正常，但它只是給出了一個布爾答案。所以，如果我把它像這樣：

alist = [4, 6, 21, 29, 37, 50] 
findSubset(alist, 76, 0, 0) 
>>> True 

但我想它返回[4, 6, 29, 37]

這是我在改變算法嘗試：

def findSubset(alist, targ, i, sumsofar, new): 
    if sumsofar == targ: 
     return new 
    if i == len(alist): 
     return [] 
    inc = findSubset(alist, targ, i+1, sumsofar+alist[i], new.append(alist[i])) 
    noninc = findSubset(alist, targ, i+1, sumsofar, new) 
    return inc or noninc 

當它被用作這樣：

alist = [4, 6, 21, 29, 37, 50] 
findSubset(alist, 76, 0, 0, []) 
>>>AttributeError: 'NoneType' object has no attribute 'append' 

我必須做些什麼才能使它工作，甚至有可能嗎？

Answer 1

我下面的代碼工作：

def findSubset(alist, targ, i, sumsofar, listsofar): 
    if sumsofar == targ: 
     return True, listsofar 
    if i == len(alist): 
     return False, listsofar 
    inc, inclistsofar = findSubset(alist, targ, i+1, sumsofar+alist[i], listsofar + [alist[i]]) 
    noninc, noninclistsofar = findSubset(alist, targ, i+1, sumsofar, listsofar) 

    if inc: 
     return inc, inclistsofar 
    else: 
     return noninc, noninclistsofar 

alist = [4, 6, 21, 29, 37, 50] 
print findSubset(alist, 76, 0, 0, []) 

list.append（）是一個就地操作。它返回None類型，但是你需要傳遞一個列表作爲參數。

Answer 2

李恆豐改進解決方案。使用默認參數，允許在沒有零點一個更好的呼叫和空列表find_subset(alist, 76)：基於評論從Blckknght

def find_subset(alist, targ, i=0, sumsofar=0, listsofar=None): 
    if listsofar is None: 
     listsofar = [] 
    if sumsofar == targ: 
     return True, listsofar 
    if i == len(alist): 
     return False, listsofar 
    inc, inclistsofar = find_subset(alist, targ, i+1, sumsofar + alist[i], listsofar + [alist[i]]) 
    noninc, noninclistsofar = find_subset(alist, targ, i+1, sumsofar, listsofar) 

    if inc: 
     return inc, inclistsofar 
    else: 
     return noninc, noninclistsofar 

alist = [4, 6, 21, 29, 37, 50] 
print(find_subset(alist, 76)) 

UPDATE

進一步的改進：

def find_subset(alist, targ, i=0, sumsofar=0, listsofar=None): 
    if listsofar is None: 
     listsofar = [] 
    if sumsofar == targ: 
     return listsofar 
    if i == len(alist): 
     return None 
    inclistsofar = find_subset(alist, targ, i+1, sumsofar + alist[i], 
           listsofar + [alist[i]]) 
    if inclistsofar: 
     return inclistsofar 
    else: 
     noninclistsofar = find_subset(alist, targ, i+1, sumsofar, listsofar) 
     return noninclistsofar 

alist = [4, 6, 21, 29, 37, 50] 
print(find_subset(alist, 76)) 
print(find_subset(alist, 100)) 
print(find_subset(alist, 1000)) 
print(find_subset(alist, 4)) 
print(find_subset(alist, 17)) 

輸出：

[4, 6, 29, 37] 
[21, 29, 50] 
None 
[4] 
None