отображение подмножества в рекурсивном алгоритме подмножества суммы

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

Улучшение решения Hengfeng Li. Используйте параметры по умолчанию, чтобы позволить более хороший вызов без нулей и пустого списка find_subset(alist, 76):

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

Дальнейшие усовершенствования, основываясь на комментарий от Blckknght:

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