LeetCode与VS Code中combinationSum4代码输出不一致问题

问题重现 #

你在LeetCode第377题中使用带默认参数memo={}的递归记忆化解法时，遇到了跨测试用例的结果错误：测试用例nums=[9], target=3在本地VS Code输出正确的0，但在LeetCode上输出4；将memo改为类成员变量后，代码恢复正常。

出错的代码：

class Solution:
    def combinationSum4(self, nums: List[int], target: int,memo={}) -> int:
        if target in memo:
            return memo[target]
        if target==0:
            return 1
        if target<0:
            return 0
        a=0
        for i in nums:
            a+=self.combinationSum4(nums,target-i,memo)
        memo[target]=a
        return memo[target]

修正后的代码：

class Solution:
    def __init__(self):
        self.memo={}
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if target in self.memo:
            return self.memo[target]
        if target==0:
            return 1
        if target<0:
            return 0
        a=0
        for i in nums:
            a+=self.combinationSum4(nums,target-i)
        self.memo[target]=a
        return self.memo[target]

核心原因：Python可变默认参数的初始化特性 #

• Python中，可变默认参数（比如memo={}）只会在函数定义时初始化一次，而不是每次调用函数时重新创建。这个字典会绑定在函数对象上，所有对该函数的调用——不管是同一个类实例还是不同实例——都会共享这个字典。
• LeetCode的运行环境会复用函数/类实例来执行多个测试用例。前一个测试用例运行时，memo会被填充缓存数据；后续测试用例调用combinationSum4时，会直接使用这个已经被修改过的memo，导致旧的缓存数据干扰当前测试用例的计算，最终输出错误结果。
• 本地VS Code中你通常单次运行单个测试用例，memo没有被之前的测试数据污染，所以结果正确。

你可以在本地做个简单验证：

class Test:
    def func(self, x, memo={}):
        memo[x] = memo.get(x, 0) + 1
        print(memo)

t1 = Test()
t1.func(1)  # 输出 {1:1}
t1.func(2)  # 输出 {1:1, 2:1}

t2 = Test()
t2.func(3)  # 输出 {1:1, 2:1, 3:1} —— 不同实例调用函数时共享了同一个memo

而将memo改为类成员变量后，每个Solution实例都拥有独立的memo字典。LeetCode为每个测试用例创建新的类实例时，都会初始化全新的memo，不会出现跨测试用例的数据污染。

其他可行的修正方案 #

除了使用类成员变量，还可以将默认参数设为None，在函数内部动态初始化：

class Solution:
    def combinationSum4(self, nums: List[int], target: int, memo=None) -> int:
        if memo is None:
            memo = {}
        if target in memo:
            return memo[target]
        if target==0:
            return 1
        if target<0:
            return 0
        a=0
        for i in nums:
            a+=self.combinationSum4(nums,target-i,memo)
        memo[target]=a
        return memo[target]

这样每次调用函数时，若未传入memo，都会创建新的空字典，彻底避免跨调用的缓存污染。

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