为何LeetCode官方题解比我的LeetCode 416解法快10倍？

我原以为自己写出了LeetCode 416题的最优DP解法，但实际运行时我的解法比官方题解慢10倍，请问这是为什么？

我的代码 #

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        dp = {}
        def backtracking(index, subset_total):
            if index == (len(nums) - 1):
                if subset_total == target:
                    return True
                else:
                    return False
            if (index, subset_total) in dp:
                return dp[(index, subset_total)]
            dp[(index, subset_total)] = backtracking(index+1, subset_total) or backtracking(index+1, subset_total + nums[index])
            return dp[(index, subset_total)]
        return backtracking(0,0)

LeetCode官方题解 #

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        @lru_cache(maxsize=None)
        def dfs(nums: Tuple[int], n: int, subset_sum: int) -> bool:
            # Base cases
            if subset_sum == 0:
                return True
            if n == 0 or subset_sum < 0:
                return False
            result = (dfs(nums, n - 1, subset_sum - nums[n - 1])
                    or dfs(nums, n - 1, subset_sum))
            return result

        # find sum of array elements
        total_sum = sum(nums)

        # if total_sum is odd, it cannot be partitioned into equal sum subsets
        if total_sum % 2 != 0:
            return False

        subset_sum = total_sum // 2
        n = len(nums)
        return dfs(tuple(nums), n - 1, subset_sum)

性能差异的核心原因 #

• 缓存实现效率天差地别：官方用的@lru_cache是CPython底层用C实现的缓存机制，存取速度远快于你手动用Python字典dp = {}做缓存。字典的增删改查都是Python层面的操作，而lru_cache直接绕开了很多Python解释器的开销，这是性能差距的主要来源之一。

• 终止条件的剪枝效率不同：

  • 你的代码要递归到最后一个元素才判断是否满足目标，而官方题解在subset_sum == 0时直接返回True，一旦找到符合条件的子集就立即终止递归，不用再往下走，能提前剪掉大量无效分支。
  • 官方还额外处理了subset_sum < 0的情况，直接返回False，避免了很多无意义的递归调用，进一步减少了计算量。

• 递归分支的短路时机：官方递归时先尝试「选当前元素」的分支，再尝试「不选」的分支。由于or操作符的短路特性，只要前面的分支返回True，后面的分支就不会执行。如果测试用例中选元素更容易快速凑出目标和，这种顺序能更早触发短路，减少递归次数。

• 参数传递的细节：官方把nums转成tuple传入递归函数（因为list不可哈希，无法被lru_cache缓存），而你的代码每次递归都要访问外部的nums列表，虽然这一点影响不如前几点大，但也是潜在的性能损耗点。

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