在子集和的递归算法中显示子集

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

但我想 return [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() 是就地操作。它是 returns 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))

更新

根据 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

在子集和的递归算法中显示子集

Display subset in recursive algorithm for subset sum

python

recursion

subset-sum