为何bestSum函数返回的列表会追加无关元素？

你的代码核心问题是直接修改了递归返回的可变列表对象，导致memo缓存的结果被污染，后续递归调用拿到的是已经被修改过的数组，最终生成错误的长组合。

具体来说，这段代码：

remaindercombo.append(num)

remaindercombo是递归调用返回的列表（可能已经被存入memo），直接append会修改原列表，当其他分支再次访问memo中的该值时，拿到的是已经添加了新元素的版本，从而导致组合长度异常增长。

修复方案 #

创建新的列表来存储当前组合，避免修改原列表：

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

    shortcombo = None
    
    for num in numbers:
        remainder = targetsum - num
        remaindercombo = bestsum(remainder, numbers, memo)
        
        if remaindercombo is not None:
            # 创建新列表，不修改原remaindercombo
            new_combo = remaindercombo + [num]
            if shortcombo is None or len(new_combo) < len(shortcombo):
                shortcombo = new_combo
    memo[targetsum] = shortcombo 
    return shortcombo

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

修复原理 #

• 使用remaindercombo + [num]创建新列表，原递归返回的列表（包括memo中缓存的）不会被修改，保证每个递归分支的组合都是独立的。
• 这样memo中存储的始终是对应targetsum的最短组合，后续调用能正确获取到未被篡改的缓存值。

运行修复后的代码，就能得到你期望的输出：

[7]
[5, 3]
[4, 4]
[25, 25, 25, 25]

内容的提问来源于stack exchange，提问作者singam suresh