题目:
题解:
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)