Bestsum记忆化函数输出结果异常问题排查求助

异常原因 #

1. 可变默认参数的陷阱 #

Python中函数的默认参数在函数定义阶段就会被初始化，而非每次调用时重新创建。你的代码用memo={}作为默认参数，意味着多次调用bestsum若不手动传入memo，会复用同一个字典，之前调用的残留数据会直接干扰后续计算，导致结果混乱。

2. 直接修改递归返回的列表引用 #

代码中result.append(i)直接修改了递归返回的列表（该列表可能是从memo中取出的引用），这会导致memo中存储的原始列表被意外篡改。后续递归调用拿到的是已被修改过的列表，最终让最短组合的判断逻辑完全失效。

比如测试bestsum(15,[3,2,5])时，先遍历3，递归得到的列表被append(3)修改，memo里对应余数的结果被篡改，后续遍历2和5时拿到的是变长的错误列表，最终错误选择了全3的组合。

解决方法 #

1. 修复可变默认参数问题 #

将memo的默认参数改为None，在函数内部初始化空字典，确保每次未传memo的调用都使用新字典：

def bestsum(targetsum, numbers, memo=None):
    if memo is None:
        memo = {}

2. 避免修改原始列表引用 #

不要直接对递归返回的result执行append操作，而是创建新列表存储当前组合：

combination = result + [num]

这样既不会修改memo中的原始数据，也能正确生成当前路径的组合。

修正后的完整代码 #

def bestsum(targetsum, numbers, memo=None):
    if memo is None:
        memo = {}
    if targetsum in memo:
        return memo[targetsum]
    if targetsum == 0:
        return []
    elif targetsum < 0:
        return None
    shortest = None

    for num in numbers:
        remainder = targetsum - num
        result = bestsum(remainder, numbers, memo)
        if result is not None:
            combination = result + [num]
            if shortest is None or len(combination) < len(shortest):
                shortest = combination
    
    memo[targetsum] = shortest
    return shortest

测试验证 #

• 调用print(bestsum(15, [3,2,5]))，输出正确最短组合[5,5,5]
• 调用print(bestsum(15, [5,2,3]))，同样输出[5,5,5]
• 调用print(bestsum(100, [5,3,2,25]))，输出最优解[25,25,25,25]

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