Function if True return 组合列表

Question

我正在关注动态规划视频。但是，对于下面显示的给定数字集，return 为 False。它应该显示 [3,4]

如果我将“组合”更改为 True。它将 return 正确。但是我想改为显示组合。

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

这里的问题是您正在检查 return 值是否为 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。

Function if True return 组合列表

Fuction if True return list of combination

python

memoization