494. 目标和（Target Sum）
难度：中等 | 主题：动态规划、0/1 背包、回溯
题目
给你一个整数数组 nums 和一个整数 target。向数组中的每个整数前添加 ’+’ 或 ’-‘，然后串联起所有整数，可以构造一个表达式。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。
示例
输入：nums = [1,1,1,1,1], target = 3
输出：5
思路
先讲个故事：天平砝码
你有一组砝码，每个砝码可以放在天平左边（正号）或右边（负号）。你希望天平最终指向某个刻度 target。
你突然意识到：左边总重 - 右边总重 = target，所有砝码总重固定。那不就是从砝码中选一些放左边，剩下的放右边，使「左边 - 右边 = target」吗？
两个方程联立，就变成了一个简单的”凑数”问题。
引导式推导：从加减号到背包
第 1 层：问题转化
设正数和为 P，负数和为 N（绝对值）。则：
-
P - N = target（题目要求） -
P + N = sum(nums)（所有数之和）
两式相加：2P = target + sum
所以：P = (target + sum) / 2
问题变成：从 nums 中选若干数，凑成和为 P 的方案数。这是0/1 背包计数。
前提：(target + sum) 必须是偶数且 ≥ 0。
graph LR A["加减号问题"] -->|P - N = target| B["P = (sum+target)/2"] B -->|0/1背包计数| C["dp[j] = 凑成 j 的方案数"] C -->|循环倒序| D["dp[j] += dp[j-num]"]
第 2 层：DFS 暴力
每个数要么正要么负，2ⁿ 种组合。n=20 勉强，n=30+ 爆。
第 3 层：DP 计数
与 416分割等和子集 的”判断能否”不同，本题求”有多少种方案”：
| 问题 | 416 判断型 | 494 计数型 |
|---|---|---|
| 状态含义 | dp[j] = 能否凑出 | dp[j] = 方案数 |
| 转移 | dp[j] or dp[j-num] | dp[j] += dp[j-num] |
| 初始化 | dp[0] = True | dp[0] = 1 |
第 4 层：处理 nums 中的 0
如果 nums 里有 0，加正号或负号不影响结果。但 dp[0] 含义不变——“什么都不选”仍是 1 种方案。转移时 dp[j] += dp[j-0] = dp[j] + dp[j]，方案数翻倍。
代码
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
# 剪枝：P 必须是整数且非负
if (target + total) % 2 != 0 or target + total < 0:
return 0
P = (target + total) // 2
dp = [0] * (P + 1)
dp[0] = 1
for num in nums:
for j in range(P, num - 1, -1):
dp[j] += dp[j - num]
return dp[P]
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n × P) | n 数组长度，P 正子集目标和 |
| 空间 | O(P) | 一维 DP 数组 |
实战考量
频率分析
出现在：字节/阿里/拼多多 二面背包进阶题。约 35% 的 AI Agent 会作为 416 的 follow-up——判断版 → 计数版，考察 DP 变体能力。
延伸思考
Q：为什么能转化为背包问题？
A：把加减号看作分两组——正数组和负数组。推出 P - N = target 和 P + N = sum，联立得 P = (target + sum) / 2。这个推导是最爱的”问题转化”考点。
Q：为什么 dp[0] = 1 而不是 0？
A：凑成 0 有一种方案——什么都不选。计数 DP 基线是”1 种方案”，不是判断型的 True。
Q：为什么内层倒序？
A：0/1 背包约束——每个数只用一次。正序时 dp[j-num] 可能已包含当前 num 的贡献，相同数被多次使用。
Q：nums 里有 0 怎么办？
A：0 的符号选择不影响结果，但转移时 dp[j] += dp[j-0] 相当于 dp[j] *= 2——因为 0 有两种符号。
Q：回溯解法怎么做？
A：每个数 ’+’ 或 ’-‘，DFS 遍历 2ⁿ 种组合。O(2ⁿ) 会超时，仅用于对比理解。
易错点
-
漏剪枝条件：
(target+total) % 2 != 0和target+total < 0，缺一不可 -
dp[0]写成 0 或 True（计数 DP 必须是 1） -
内层正序 → 完全背包
-
dp[j] += dp[j-num]写成= dp[j-num]→ 丢不选当前数的方案
生活类比
天平砝码 → 0/1 背包计数 → 加减号组合
给每个砝码决定放左边还是右边，本质是从中挑出一些放左边（正数），剩下的放右边（负数）。
就像点菜——你选一些菜自己吃（正），朋友吃剩下的（负），最后账单差值是 target。
计数 DP 就是数有多少种分法，不关心能不能分，只关心有几种方法能分。
相关题目
→ 返回题单：LeetCode学习路线图 > 十三、动态规划
速记卡（面试闪卡）
Q1：一句话讲清「494. 目标和（Target Sum）」到底是什么？
A：把加减号问题转成 0/1 背包：凑出正数和 P=(sum+target)/2 的方案数。
Q2：题目 —— 怎么理解？
A：像天平砝码：给数组 nums 和 target，每个数前加 + 或 - 拼表达式，求结果等于 target 的不同表达式数目。示例 nums=[1,1,1,1,1],target=3 → 5 种。
Q3：思路 —— 怎么理解？
A：像分两拨砝码：设正数和 P、负数和 N，有 P-N=target 且 P+N=sum，联立得 P=(target+sum)/2。问题变成从 nums 选若干凑出和 P 的方案数——标准 0/1 背包计数。前提 (target+sum) 是偶数且 ≥0，否则 0 种。
Q4：代码 —— 怎么理解？
A：剪枝：(target+total)%2!=0 或 <0 返回 0；P=(target+total)//2；dp=[0]*(P+1)，dp[0]=1；for num：for j in range(P,num-1,-1)：dp[j]+=dp[j-num]。返回 dp[P]。内层倒序保证每个数只用一次。
Q5：复杂度 —— 怎么理解？
A：像背包大小决定：时间 O(n×P)（n 长度，P 正子集目标和）；空间 O(P) 一维 DP。有 0 时转移 dp[j]+=dp[j-0] 相当于翻倍（0 两种符号）。
Q6：核心速记主线有哪些？
-
转化：P-N=target 联立 P+N=sum → P=(sum+target)/2
-
0/1 背包计数：dp[j] 是方案数，dp[0]=1（什么都不选）
-
内层倒序防完全背包；转移 dp[j]+=dp[j-num] 别写成 =
-
判 416 同族但 416 是判断型（dp[j]=or），494 是计数型
口诀
A：目标和转背包，
正负分成两拨；
P 等于 sum 加 target 半，
倒序累加方案数。