Python | Leetcode Python题解之第494题目标和

题目：

题解：

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:cache = {}      # 记忆化单元# @functools.cache  # Python functools自带记忆化单元【启用后可省去自定义cache单元】def dfs(i, summ, t):'''summ: 前i个元素的表达式之和; t: 目标值'''if (i, summ) in cache:          # 记忆化：已存在，直接返回return cache[(i, summ)]if i == len(nums):              # 遍历完了全部的元素，递归中止if summ == t:               # 找到了一个满足要求的组合cache[(i, summ)] = 1else:cache[(i, summ)] = 0return cache[(i, summ)]pos_cnt = dfs(i+1, summ + nums[i], t)       # nums[i]前面添加'+'号neg_cnt = dfs(i+1, summ - nums[i], t)       # nums[i]前面添加'-'号cache[(i, summ)] = pos_cnt + neg_cnt        # 以上两种情况的组合数之和return cache[(i, summ)]return dfs(0, 0, target)