LeetCode 494. 目标和

题目描述

给你一个非负整数数组 nums 和一个整数 target。向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数构成一个表达式。求可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例：

输入：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

提示：

• 1 ≤ nums.length ≤ 20
• 0 ≤ nums[i] ≤ 1000
• 0 ≤ sum(nums[i]) ≤ 1000
• -1000 ≤ target ≤ 1000

解题过程循序渐进讲解

第一步：理解问题本质

我们有一个数组 nums，每个数字前可以放 + 或 -，最终求和等于 target。
这相当于将数组分成两个子集：

• 前面放 + 的数字集合（记其和为 sum(P)）
• 前面放 - 的数字集合（记其和为 sum(N)）

那么有：

sum(P) - sum(N) = target

设数组总和为 total，则有：

sum(P) + sum(N) = total

将两式相加：

2 * sum(P) = target + total

所以：

sum(P) = (target + total) / 2

问题转化：
从 nums 中选若干个数，使它们的和等于 (target + total) / 2，计算有多少种不同的选法。
这里 sum(P) 必须是非负整数，所以要求：

1. target + total 必须是非负偶数，否则无法实现，直接返回 0。
2. 因为 nums[i] 非负，所以选出的子集和也是非负的。

这样就变成了子集和问题（给定若干数字，选出一些使得和等于某个值）。

第二步：动态规划定义

定义 dp[j] 表示：填满容量为 j 的背包，有多少种不同的方法。
这里的“容量”就是目标子集和 (target + total) / 2，每个数字的“重量”是它的值，数字可以放入（取正号）或不放入（取负号），并且数字只能使用一次 → 这是 0-1背包问题。
dp[0] = 1，表示容量为 0 的背包只有一种方法：什么都不选。

状态转移：
对于每个数字 num，我们要更新 dp 数组，为了避免同一数字重复使用，应该倒序遍历 j 从 targetSum 到 num：

dp[j] = dp[j] + dp[j - num]

含义：不选当前数字的方法数（dp[j] 原来值） + 选当前数字的方法数（dp[j - num]）。

第三步：示例推演

以 nums = [1,1,1,1,1], target = 3 为例：
total = 5
targetSum = (3+5)/2 = 4
我们要从 5 个 1 中选若干个数，使它们的和等于 4，问有多少种选法。
显然，选 4 个 1 出来即可，组合数为 C(5,4) = 5。

用 DP 计算：
初始化 dp = [1,0,0,0,0]（容量 0~4）

• 处理第一个 1：
  j 从 4 到 1 倒序更新：
  j=4: dp[4] += dp[3] (0) → dp[4]=0
  j=3: dp[3] += dp[2] (0) → 0
  j=2: dp[2] += dp[1] (0) → 0
  j=1: dp[1] += dp[0] (1) → dp[1]=1
  此时 dp = [1,1,0,0,0]

• 处理第二个 1：
  j=4: dp[4] += dp[3] (0) → 0
  j=3: dp[3] += dp[2] (0) → 0
  j=2: dp[2] += dp[1] (1) → dp[2]=1
  j=1: dp[1] += dp[0] (1) → dp[1]=2
  dp = [1,2,1,0,0]

• 处理第三个 1：
  j=4: dp[4] += dp[3] (0) → 0
  j=3: dp[3] += dp[2] (1) → dp[3]=1
  j=2: dp[2] += dp[1] (2) → dp[2]=3
  j=1: dp[1] += dp[0] (1) → dp[1]=3
  dp = [1,3,3,1,0]

• 处理第四个 1：
  j=4: dp[4] += dp[3] (1) → dp[4]=1
  j=3: dp[3] += dp[2] (3) → dp[3]=4
  j=2: dp[2] += dp[1] (3) → dp[2]=6
  j=1: dp[1] += dp[0] (1) → dp[1]=4
  dp = [1,4,6,4,1]

• 处理第五个 1：
  j=4: dp[4] += dp[3] (4) → dp[4]=5
  j=3: dp[3] += dp[2] (6) → dp[3]=10
  j=2: dp[2] += dp[1] (4) → dp[2]=10
  j=1: dp[1] += dp[0] (1) → dp[1]=5
  dp = [1,5,10,10,5]

最终 dp[4] = 5，与预期一致。

第四步：边界情况

1. 如果 target > total 或 target < -total，则不可能实现，因为即使全正或全负也达不到。
2. 如果 (target + total) 是奇数，那么无解，因为 sum(P) 必须是整数。
3. 如果转化后的目标子集和 targetSum < 0，也要返回 0（但由条件可知 targetSum ≥ 0）。

第五步：复杂度与实现

• 时间复杂度：O(n * targetSum)，其中 targetSum = (target+total)/2 ≤ 2000（因为 total ≤ 1000，target ≤ 1000 的绝对值，实际最大 2000），n ≤ 20，所以可行。
• 空间复杂度：O(targetSum)。

def findTargetSumWays(nums, target):
    total = sum(nums)
    if (target + total) % 2 != 0 or total < abs(target):
        return 0
    targetSum = (target + total) // 2
    if targetSum < 0:
        return 0
    
    dp = [0] * (targetSum + 1)
    dp[0] = 1
    for num in nums:
        for j in range(targetSum, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[targetSum]

第六步：思考其他方法

本题还可以用DFS回溯（因为 n ≤ 20，2^20 ≈ 1e6 可行），但会超时在更大边界。
用记忆化搜索（DFS+缓存）可过，状态是 (index, current_sum)，但空间略大。
动态规划是最优的通用解法，尤其适用于 n 不大但数字总和不太大的情况。