题目描述
思路解析
一句话答案：LeetCode 494 目标和的最优解是转化成 0-1 背包计数：设取正号的数之和为 P，由 P = (sum + target) / 2 把「添加减号」翻译成「选出和为 P 的子集有几种」，再用 dp[w] += dp[w - x]、容量倒序的一维背包数方案。时间 O(n·P)、空间 O(P)，无解时直接返回 0。
目标和这道题在问什么
给数组 nums 和目标值 target，要给每个数前面添一个加号或减号，使整个表达式的和恰好等于 target，问有多少种不同的添法。注意问的是方案数而不是能不能——每个数都必须用且恰好用一次，只是符号二选一。比如 nums=[1,1,1,1,1]、target=3，共有 5 种添法。
为什么加减号问题能转成子集和计数
直接搜索每个数取正取负，是 2 的 n 次方条路径的暴力枚举。转化的钥匙是一组方程：把取正号的那些数之和记作 P，取负号的数之和（取绝对值）记作 N，那么 P + N = sum（所有数都用了），P - N = target（表达式的值）。两式相加解出 P = (sum + target) / 2。
也就是说，一种符号添法完全由「哪些数取正号」决定，而这个正号集合的和必须恰好是 P。反过来，任何一个和为 P 的子集，把它里面的数标正、其余标负，就是一种合法添法。两边一一对应，所以「添符号凑 target 的方案数」等于「选出和为 P 的子集的个数」——问题从指数搜索变成了背包计数。
这个转化还自带两条判定：P 必须是非负整数，所以 (sum + target) 是奇数、或 sum < |target| 时无解，直接返回 0，不用进主循环。
dp 怎么定义，为什么 dp[0] 初始化为 1
定义 dp[w] 为：用目前已考虑的数，凑出和恰好为 w 的方案数，最终答案是 dp[P]。起点 dp[0] = 1——空集是凑出 0 的唯一方式，算一种方案。这个 1 是全表的种子：所有非零方案数都是从它一层层加出来的，写成 0 整张表恒为 0。
和判断「能不能」的布尔背包（如 LeetCode 416 分割等和子集）相比，这里 dp 存的是「有几种」，逻辑或换成加法，其余框架完全一致。
转移为什么是相加，容量为什么必须倒序
每加入一个数 x，凑出 w 的方案分成两类：不选 x 的方案，个数就是原来的 dp[w]；选 x 的方案，等于先凑出 w - x 再放入 x，个数是 dp[w - x]。一种方案不可能既含 x 又不含 x，两类不重叠也不遗漏，按加法原理 dp[w] += dp[w - x]。
内层容量必须从 P 倒序扫到 x：转移引用的 dp[w - x] 必须是本轮更新前的旧值，代表「还没用过 x」的状态。正序扫的话 dp[w - x] 可能已被 x 更新过，等于让同一个数用了两次，方案被重复计数。倒序就是「每个数只用一次」的代码化身。
复杂度多少，含 0 的元素会出问题吗
时间复杂度 O(n·P)：n 个数各扫一遍长度为 P 的容量轴，P = (sum + target) / 2。空间 O(P)，一维滚动数组。
一个值得想清楚的细节：nums 里若有 0，它取正取负都不改变和，但两种符号是两种不同方案。这套 dp 天然处理正确——x = 0 时转移变成 dp[w] += dp[w]，每个状态的方案数恰好翻倍，正好对应 0 的两种添法，不需要任何特判。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
加减号问题被翻译成「选哪些数当正号 → 子集和 = P 的方案数」。dp[i][s] = 用前 i 个数凑出和 s 的方案数。
第 0 行 = 一个数都没用。只有「容量 0」有 1 种凑法（空集），其余容量都是 0 种。这是所有递推的起点。
算 dp[1][0]：容量 0 比第 1 个数 1 还小，放不进，只能照搬上方 dp[0][0] = 1 种。
填入 dp[1][0] = 1 种。
算 dp[1][1]：不选第 1 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[0][0] = 1 种。两种填法不重叠，相加。
填入 dp[1][1] = 1 种。
算 dp[1][2]：不选第 1 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[0][1] = 0 种。两种填法不重叠，相加。
填入 dp[1][2] = 0 种。
算 dp[1][3]：不选第 1 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[0][2] = 0 种。两种填法不重叠，相加。
填入 dp[1][3] = 0 种。
算 dp[1][4]：不选第 1 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[0][3] = 0 种。两种填法不重叠，相加。
填入 dp[1][4] = 0 种。
算 dp[2][0]：容量 0 比第 2 个数 1 还小，放不进，只能照搬上方 dp[1][0] = 1 种。
填入 dp[2][0] = 1 种。
算 dp[2][1]：不选第 2 个数（值 1）= 上方 1 种；选它 = 先腾出 1 看左上 dp[1][0] = 1 种。两种填法不重叠，相加。
填入 dp[2][1] = 2 种。
算 dp[2][2]：不选第 2 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[1][1] = 1 种。两种填法不重叠，相加。
填入 dp[2][2] = 1 种。
算 dp[2][3]：不选第 2 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[1][2] = 0 种。两种填法不重叠，相加。
填入 dp[2][3] = 0 种。
算 dp[2][4]：不选第 2 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[1][3] = 0 种。两种填法不重叠，相加。
填入 dp[2][4] = 0 种。
算 dp[3][0]：容量 0 比第 3 个数 1 还小，放不进，只能照搬上方 dp[2][0] = 1 种。
填入 dp[3][0] = 1 种。
算 dp[3][1]：不选第 3 个数（值 1）= 上方 2 种；选它 = 先腾出 1 看左上 dp[2][0] = 1 种。两种填法不重叠，相加。
填入 dp[3][1] = 3 种。
算 dp[3][2]：不选第 3 个数（值 1）= 上方 1 种；选它 = 先腾出 1 看左上 dp[2][1] = 2 种。两种填法不重叠，相加。
填入 dp[3][2] = 3 种。
算 dp[3][3]：不选第 3 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[2][2] = 1 种。两种填法不重叠，相加。
填入 dp[3][3] = 1 种。
算 dp[3][4]：不选第 3 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[2][3] = 0 种。两种填法不重叠，相加。
填入 dp[3][4] = 0 种。
算 dp[4][0]：容量 0 比第 4 个数 1 还小，放不进，只能照搬上方 dp[3][0] = 1 种。
填入 dp[4][0] = 1 种。
算 dp[4][1]：不选第 4 个数（值 1）= 上方 3 种；选它 = 先腾出 1 看左上 dp[3][0] = 1 种。两种填法不重叠，相加。
填入 dp[4][1] = 4 种。
算 dp[4][2]：不选第 4 个数（值 1）= 上方 3 种；选它 = 先腾出 1 看左上 dp[3][1] = 3 种。两种填法不重叠，相加。
填入 dp[4][2] = 6 种。
算 dp[4][3]：不选第 4 个数（值 1）= 上方 1 种；选它 = 先腾出 1 看左上 dp[3][2] = 3 种。两种填法不重叠，相加。
填入 dp[4][3] = 4 种。
算 dp[4][4]：不选第 4 个数（值 1）= 上方 0 种；选它 = 先腾出 1 看左上 dp[3][3] = 1 种。两种填法不重叠，相加。
填入 dp[4][4] = 1 种。
算 dp[5][0]：容量 0 比第 5 个数 1 还小，放不进，只能照搬上方 dp[4][0] = 1 种。
填入 dp[5][0] = 1 种。
算 dp[5][1]：不选第 5 个数（值 1）= 上方 4 种；选它 = 先腾出 1 看左上 dp[4][0] = 1 种。两种填法不重叠，相加。
填入 dp[5][1] = 5 种。
算 dp[5][2]：不选第 5 个数（值 1）= 上方 6 种；选它 = 先腾出 1 看左上 dp[4][1] = 4 种。两种填法不重叠，相加。
填入 dp[5][2] = 10 种。
算 dp[5][3]：不选第 5 个数（值 1）= 上方 4 种；选它 = 先腾出 1 看左上 dp[4][2] = 6 种。两种填法不重叠，相加。
填入 dp[5][3] = 10 种。
算 dp[5][4]：不选第 5 个数（值 1）= 上方 1 种；选它 = 先腾出 1 看左上 dp[4][3] = 4 种。两种填法不重叠，相加。
填入 dp[5][4] = 5 种。
看最后一行的第 4 列 dp[5][4] = 5：用全部 5 个数凑出子集和 4 有 5 种 —— 也就是给 nums 添正负号凑出 3 的方法数 = 5。
几个边界自己心算一遍。
两个高频追问。
参考代码
def findTargetSumWays(nums, target): s = sum(nums) if (s + target) % 2 or s < abs(target): return 0 P = (s + target) // 2 dp = [1] + [0] * P # dp[0]=1 for x in nums: for w in range(P, x - 1, -1): dp[w] += dp[w - x] return dp[P]复杂度
- 时间：O(n·P)，n 个数 × 每个数扫一遍容量 P
- 空间：O(P)，一维滚动数组，P=(sum+target)/2
易错点
面试追问把动画讲成自己的话
追问为什么能把加减号问题转成子集和计数？
追问nums 含 0 会怎样？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
交错字符串
LeetCode 97 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题