为什么我的备忘录对象打印所有组合？

Question

我找到数组中等于目标总和的最短数字组合：

def bestSum(targetSum, numbers, memo = None):
    if memo is None:
        memo = {}
    if targetSum in memo:
        return memo[targetSum]
    if targetSum == 0:
        return []
    if targetSum < 0:
        return None
    shortestCombination = None
    for n in numbers:
        remainder = targetSum - n
        remainderCombination = bestSum(remainder, numbers, memo)
        if remainderCombination is not None:
            remainderCombination.append(n)
            combination = remainderCombination
        # if the combination is shorter than the shortest, update it
            if shortestCombination is None or len(combination) < len(shortestCombination):
                shortestCombination = combination
    memo[targetSum] = shortestCombination
    return shortestCombination

print(bestSum(100, [1, 2, 5, 25]))   # [25, 25, 25, 25]
print(bestSum(7, [5, 3, 4, 7]))  # 7
print(bestSum(8, [2, 3, 5]))  # [3, 5]
print(bestSum(8, [1, 4, 5]))  # [4, 4]

蛮力有效，但对于记忆解决方案，只有第二个和第三个答案匹配（例如#7和#[5,3]）。我似乎无法修复它。

Answer 1

您正在修改存储在备忘录中的列表，从而废弃该备忘录。如果您只是在修改之前复制返回的列表，您的代码就可以正常工作：

def bestSum(targetSum, numbers, memo = None):
    if memo is None:
        memo = {}
    if targetSum in memo:
        return memo[targetSum]
    if targetSum == 0:
        return []
    if targetSum < 0:
        return None
    shortestCombination = None
    for n in numbers:
        remainder = targetSum - n
        combination = bestSum(remainder, numbers, memo)
        if combination is not None:
            combination = combination + [n]
            if shortestCombination is None or len(combination) < len(shortestCombination):
                shortestCombination = combination
    if shortestCombination:
        memo[targetSum] = shortestCombination
        return shortestCombination

print(bestSum(100, [1, 2, 5, 25]))   # [25, 25, 25, 25]
print(bestSum(7, [5, 3, 4, 7]))  # 7
print(bestSum(8, [2, 3, 5]))  # [3, 5]
print(bestSum(8, [1, 4, 5]))  # [4, 4]