带记忆化的bestSum递归函数列表引用导致缓存值错误问题

你的推测完全正确，核心问题是Python中可变对象的引用传递特性：

• 列表属于可变对象，代码中返回、存储、修改的都是列表的内存引用，不是独立的副本
• 当某个target的结果列表被存入记忆字典后，后续其他递归层级如果拿到这个引用并执行append操作，会直接修改字典中已经存储的列表内容，导致记忆值被污染

比如你遇到的异常情况：

1. 第一次计算bestSum(2, numbers, dict)时得到结果[2]，存入字典dict[2] = [2]
2. 后续其他递归分支调用bestSum(2, numbers, dict)时，直接返回字典里[2]的引用，对这个返回值执行append(num)操作时，就把字典里的[2]改成了[2, num]，最终导致记忆值完全错误

核心思路是避免修改已经存入记忆字典的列表引用，两种常用实现方案如下：

方案1：生成新列表，不修改原返回值（推荐） #

把直接修改原列表的append操作，改为生成新列表的拼接操作，从根源上避免修改原引用：

def bestSum(target, numbers, memo):
    if target in memo:
        return memo[target]
    if target == 0:
        return []
    if target < 0:
        return None

    shortestCombination = None
    for num in numbers:
         resultCombination = bestSum(target - num, numbers, memo)
         if resultCombination is not None:
             # 不修改原resultCombination，生成全新的列表对象
             currentCombination = resultCombination + [num]
             if (shortestCombination is None or len(currentCombination) < len(shortestCombination)):
                shortestCombination = currentCombination

    memo[target] = shortestCombination
    return shortestCombination

print(bestSum(8,[4,2,7],{}))

注：这里把参数名dict改为了memo，避免覆盖Python内置的dict关键字，属于代码规范优化。

方案2：对记忆值做拷贝 #

如果要保留append的写法，就在存入和取出记忆值时都做浅拷贝，避免原记忆值被修改：

def bestSum(target, numbers, memo):
    if target in memo:
        # 取出时返回副本
        return memo[target].copy() if memo[target] is not None else None
    if target == 0:
        return []
    if target < 0:
        return None

    shortestCombination = None
    for num in numbers:
         resultCombination = bestSum(target - num, numbers, memo)
         if resultCombination is not None:
             resultCombination.append(num)
             if (shortestCombination is None or len(resultCombination) < len(shortestCombination)):
                shortestCombination = resultCombination

    # 存入时存储副本
    memo[target] = shortestCombination.copy() if shortestCombination is not None else None
    return shortestCombination

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