LeetCode Target Sum递归加@cache缓存返回错误结果问题

问题复现 #

求解目标和题目时使用的递归DFS代码如下：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        count = 0
        @cache
        def dfs(i, cum_sum):
            nonlocal count
            if i >= len(nums):
                if cum_sum == target:
                    count += 1
                return
            dfs(i+1, cum_sum + nums[i])
            dfs(i+1, cum_sum - nums[i])

        dfs(0, 0)
        return count

运行时出现异常现象：

• 移除@cache装饰器，代码可正常运行返回正确结果，但时间复杂度极高容易超时
• 保留@cache装饰器，代码运行速度变快，但返回的结果小于正确值，答案错误

根本原因 #

问题出在@cache装饰器的运行机制和函数设计逻辑不匹配：

1. @cache是functools.lru_cache的无上限缓存版本，核心逻辑是：以函数传入的参数为key，缓存函数执行后的返回值。后续如果出现参数完全相同的调用，直接返回缓存里的返回值，不会再执行函数内部的任何代码。
2. 上述实现中的dfs函数没有定义返回值，本质是靠修改外部作用域的count变量做副作用计数，这种写法和缓存机制完全冲突：
   • 第一次访问某个(i, cum_sum)状态时，函数会正常执行，递归走完后续分支、按逻辑累加count，执行结束后缓存会记录这组参数对应的返回值为None
   • 后续其他递归路径如果再次访问到同一个(i, cum_sum)状态，缓存会直接返回之前存的None，跳过整个函数执行流程，这部分状态对应的合法路径计数完全不会被累加到count里，最终统计的路径数自然比真实值小，返回错误答案。
3. 移除@cache后没有缓存拦截，所有递归路径都会完整执行函数逻辑，所有合法路径都能被统计到，所以能返回正确结果，但因为存在大量重复状态计算，时间复杂度为O(2^n)，输入数组长度稍大就会超时。

修正方案 #

带缓存的正确写法需要让dfs函数直接返回当前状态对应的合法路径数量，完全去掉对外部计数变量的依赖，让缓存存储的结果本身就是有效计数：

from functools import cache
from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        @cache
        def dfs(i, cur_sum):
            if i == n:
                return 1 if cur_sum == target else 0
            return dfs(i+1, cur_sum + nums[i]) + dfs(i+1, cur_sum - nums[i])
        return dfs(0, 0)

这种写法下每个(i, cur_sum)状态只会计算一次，缓存的返回值就是当前状态到终点的合法路径数，既保证结果正确，时间复杂度也能降到O(n*S)（S为数组所有元素和的两倍左右），不会超时。

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