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

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):

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))

ОБНОВИТЬ

Дальнейшие улучшения, основанные на комментарии 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