canSum动态规划函数异常求助：全部返回true与预期不符

需求描述 #

实现canSum(targetSum, numbers)函数，该函数接收targetSum和数字数组作为参数，返回布尔值，判断是否可使用数组中的元素（可重复使用）生成targetSum，采用动态规划思路，输入数字均为非负数。

现有代码 #

def canSum(targetsum,numbers,memo={}):
    if targetsum in  memo:
        return memo[targetsum]
    if targetsum==0:
        return True
    if targetsum<0:
        return False
    for num in numbers:
        remainder=targetsum-num
        if (canSum(remainder,numbers,memo)==True):
            memo[targetsum]=True
            return True
    memo[targetsum]=True
    return False
print(canSum(7,[2,3]))
print(canSum(7,[5,3,4,7]))
print(canSum(7,[2,4]))
print(canSum(8,[2,3,5]))
print(canSum(300,[7,14]))

问题现象 #

调用上述测试用例时，所有输出均为True，但正确预期输出应为：

true
true
false
true
false

问题根源 #

1. 默认参数缓存污染：Python中默认参数memo={}仅在函数定义时初始化一次，后续所有调用会复用同一个字典，导致不同测试用例的缓存互相干扰。
2. 错误的缓存赋值：当遍历完所有数字都无法凑出targetSum时，代码错误地将memo[targetsum]设为True，正确值应为False。

修复后的代码 #

def canSum(targetsum, numbers, memo=None):
    # 每次调用初始化独立缓存，避免跨调用污染
    if memo is None:
        memo = {}
    if targetsum in memo:
        return memo[targetsum]
    if targetsum == 0:
        return True
    if targetsum < 0:
        return False
    for num in numbers:
        remainder = targetsum - num
        if canSum(remainder, numbers, memo):
            memo[targetsum] = True
            return True
    # 无法凑出时缓存False结果
    memo[targetsum] = False
    return False

print(canSum(7,[2,3]))      # True
print(canSum(7,[5,3,4,7]))  # True
print(canSum(7,[2,4]))      # False
print(canSum(8,[2,3,5]))    # True
print(canSum(300,[7,14]))   # False

修复说明 #

• 将默认参数memo={}改为memo=None，并在函数内部创建新字典，确保每次调用都有独立的缓存空间，避免测试用例之间的缓存干扰。
• 当确认无法凑出当前targetSum时，将缓存值设为False，正确记录状态，避免后续重复计算时返回错误结果。

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