Python带memoization的bestSum最短凑和组合算法输出错误问题

• 缩进错误：带memo版本的Python代码中，targetSum==0、targetSum<0的基础判断逻辑错误缩进在if targetSum in memo:的分支内部，仅当targetSum存在于memo时才会触发基础判断，不在memo中的目标值会直接进入递归，本身就会触发逻辑错误。
• 可变对象引用污染：Python中列表是可变对象，代码直接将递归返回的remainder_combination赋值给combination后调用append方法，本质是修改同一块内存空间的列表内容。存入memo的是列表的引用，后续修改会直接改动memo中已经缓存的结果，导致缓存值被污染，读取memo时拿到的是错误修改后的列表。对比可正常运行的JS代码可以看到，JS中用扩展运算符[...reminderCombination,num]生成了全新数组，不会修改原递归返回值，因此没有缓存污染问题。

无memo版本可以正常运行的原因是没有缓存逻辑，每次计算生成的列表只会影响当前递归分支，不会干扰其他计算过程。

1. 修正代码缩进，将基础判断逻辑移到和memo读取逻辑同级的位置。
2. 每次生成新的列表副本，不直接修改递归返回的列表，避免污染缓存。可直接用+运算符生成新列表，或对返回列表做浅拷贝后再修改。

修复后代码如下：

def bestSum(targetSum, arr, memo=None):
    # 初始化memo，避免全局变量干扰多次调用的结果
    if memo is None:
        memo = {}
    if targetSum in memo:
        return memo[targetSum]
    # 基础判断逻辑缩进修正
    if targetSum == 0:
        return []
    if targetSum < 0:
        return None

    shortestCombination = None
    for num in arr:
        remainder_combination = bestSum(targetSum - num, arr, memo)
        if remainder_combination is not None:
            # 生成新的列表副本，不修改原递归返回值
            combination = remainder_combination + [num]
            if shortestCombination is None or len(combination) < len(shortestCombination):
                shortestCombination = combination
    
    memo[targetSum] = shortestCombination
    return shortestCombination

# 测试用例
print(bestSum(10, [1,4,5]))
print(bestSum(7,[3,4,7]))
print(bestSum(20,[1,2,3,4,5,10]))
print(bestSum(3,[3,2,1]))

运行后即可输出预期的正确结果：

[5, 5]
[7]
[10, 10]
[3]

内容的提问来源于stack exchange，提问作者Denz。