如果函数为真，则返回组合列表

Question

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

如果我将“combo”更改为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]

还有一件事需要注意。我们可以通过引入一个helper函数将其作为参数传递，而不是创建一个全局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