494. 目标和

🎯 问题描述

描述：给定一个非负整数数组 nums 和一个目标整数 target，对于数组中的每个数字，可以选择给它添加 ‘+’ 或 ‘-’ 符号。返回可以使最终数组和等于目标值 target 的表达式数目。

说明：

给定数组非空，且包含非负整数
数组长度 n ≤ 20
数组中数字总和 ≤ 1000
目标值 -1000 ≤ target ≤ 1000

示例：

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：有 5 种方法让最终和为 3：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

示例 2：

1 2	输入：nums = [1], target = 1 输出：1

💻 解题思路

思路1：记忆化搜索（递归DP）

核心思想：这是一个典型的子集划分问题，可以通过递归枚举所有可能的符号组合来解决。

问题转化：

设所有添加 ‘+’ 的数字之和为 P，所有添加 ‘-’ 的数字之和为 N
我们需要 P - N = target
同时 P + N = sum(nums)
推导出：P = (target + sum(nums)) / 2
问题转化为：从数组中选出若干数字，使其和等于 P 的方案数

算法步骤：

递归定义：f(i, sum) 表示从第 i 个位置开始，当前和为 sum 时，能达到目标值的方案数
基准情况：当 i == n 时，检查当前和是否等于目标值
递归拆解：对当前数字，可以选择加 ‘+’ 或 ‘-’
记忆化：使用 @lru_cache 避免重复计算

思路1：代码实现

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        @lru_cache(None)
        def f(i: int, Sum: int) -> int:
            # 基准情况：已经处理完所有数字
            if i == n:
                return 1 if Sum == target else 0
            # 递归拆解：选择 '+' 或 '-'
            # 选择 '+'：当前和加上 nums[i]
            # 选择 '-'：当前和减去 nums[i]
            return f(i + 1, Sum + nums[i]) + f(i + 1, Sum - nums[i])
        return f(0, 0)
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n=len(nums)
        table={}
        def f(i:int,Sum:int)->int:
            if i == n:
                return 1 if Sum==target else 0
            if (i,Sum)in table:
                return table[(i,Sum)]
            cnt = f(i+1,Sum+nums[i])+f(i+1,Sum-nums[i])
            table[(i,Sum)]=cnt
            return cnt
        return f(0,0)

思路1：📊 性能分析

时间复杂度： $O(N \times S)$ $O (N \times S)$
- $N$ 是数组长度
- $S$ 是可能的和的范围，由于记忆化，每个状态只计算一次
空间复杂度： $O(N \times S)$ $O (N \times S)$
- 递归栈深度为 $O(N)$
- 记忆化缓存空间为 $O(N \times S)$