如果为True，则返回组合列表

Question

我正在关注一个动态编程视频。但是，对于下面显示的给定数字集，返回值为False。应显示[3,4]

如果我改变"；组合"；为True。它将返回True。不过我想展示一下组合。

combo = list()
def howsum(targetsum,numbers):
if targetsum == 0: return combo
if targetsum < 0: return False

for number in numbers:
remainder = targetsum - number
combo.append(number)

if howsum(remainder,numbers) == True: return combo
return False

print(howsum(7,[3,4])) #output should be [3,4]

Answer 1

这里的问题是检查返回值是否为True，而不是是否存在。空集合的真性为False，非空集合的实性为True。同样对于回溯，您需要从当前组合中pop()来尝试替代方案。

combo = list()
def howsum(targetsum, numbers):
if targetsum == 0: return combo
if targetsum < 0: return False
for number in numbers:
remainder = targetsum - number
combo.append(number)
if howsum(remainder, numbers): return combo
combo.pop()
return False

print(howsum(7, [3, 4]))  # output should be [3,4]

还有一件事需要注意。我们可以通过引入助手函数将其作为参数传递，而不是创建全局combo列表。

def howsum_helper(targetsum, numbers, combo):
if targetsum == 0: return combo
if targetsum < 0: return False
for number in numbers:
remainder = targetsum - number
combo.append(number)
if howsum_helper(remainder, numbers, combo): return combo
combo.pop()
return False
def howsum(targetsum, numbers):
return howsum_helper(targetsum, numbers, [])
print(howsum(7, [3, 4]))  # output should be [3,4]

该解决方案还假设数字列表中的数字可以被重复以达到targetSum。