两个近乎相同的LeetCode 416解法为何运行时与内存差异巨大？

两种解法的核心逻辑都是基于记忆化递归的子集和问题求解，但几个关键细节的差异导致了性能的显著差距，具体原因如下：

1. 递归分支调用顺序触发的短路优化差异 #

这是影响性能的核心因素：

• 你的解法在处理nums[i] <= target时，先调用「不选当前元素」的分支，再调用「选当前元素」的分支：

  memo[(i, target)] = check_all(i+1, target) or check_all(i+1, target-nums[i])
  

• 另一个解法则优先调用「选当前元素」的分支，再调用「不选当前元素」的分支：

  dp[(i,target)] = self.helper(dp,nums,target-nums[i],i+1) or self.helper(dp,nums,target,i+1)
  

Python的or是短路求值运算符：只要第一个表达式返回True，就会直接跳过第二个表达式的计算。在分割等和子集问题中，「选当前元素」的分支能更快将target减至0（找到有效解），因此另一个解法会更早触发短路，直接终止后续不必要的递归调用，大幅减少了函数调用次数，同时也减少了记忆化字典中存储的状态数量，这直接降低了时间和内存开销。

2. 求和操作的重复计算开销 #

• 你的解法中sum(nums)被计算了两次：一次用于判断总和奇偶性，另一次用于生成递归的target参数，这意味着数组被遍历了两次。
• 另一个解法仅计算一次sum(nums)并存储在变量中，避免了重复遍历求和的额外开销，对于大规模数组，这部分优化的影响会更明显。

3. 闭包与参数传递的细微性能差异 #

• 你的解法使用嵌套函数check_all，通过闭包访问外部作用域的nums和memo变量；另一个解法将nums和dp作为参数直接传递给类方法helper。
• 在Python中，闭包访问外部变量的开销略高于直接访问函数参数，虽然这部分差异远小于递归顺序带来的影响，但长期的递归调用会将这部分细微差异放大，进一步拉开性能差距。

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