题目描述
给数组每个数前面放一个 + 或 −，使表达式结果等于 target，求一共有多少种添符号方法。
思路解析
最直接的想法：每个数独立选 + 或 −，n 个数就是 2ⁿ 种符号组合，逐一算结果看是否等于 target。数一多就指数爆炸，而且大量子和被重复计算。
记取 + 的数之和为 P、取 − 的为 N。两式联立：P＋N=sum、P−N=target，解得 P=(sum+target)÷2。问题就变成：选一个子集，使它的和恰好等于 P，有几种选法——这正是 0-1 背包计数！状态 dp[j]=凑出和 j 的方法数，转移 dp[j]+=dp[j−x]。这里 P=(5+3)÷2=4。
建表 · dp[0]=1：表头是子集和 0 到 4。dp[j] 记「选出的数之和恰好为 j 的方法数」。dp[0]=1（空集就能凑出 0，算一种），其余先为 0。目标看 dp[4]。
放第 1 个 1：放第一个 1，内层从大到小扫：dp[1] += dp[0] = 1。意思是「用这一个 1 凑出和 1」有 1 种方法。其余格暂时凑不出，仍是 0。
放第 1 个 1 · 装不下的格：注意负例：容量 0 这格想装数字 1，j−1 会变成负数，根本装不下。所以循环只扫到 x 为止，dp[0] 永远沿用「这个数不选」的旧值 1。这保证了空集这一种方法不被破坏。
放第 2 个 1：放第二个 1：dp[2] 累加上 dp[1] 得 1，dp[1] 再累加 dp[0] 变成 2。每个 dp[j] 都把「上一个数填好的 dp[j−1]」叠进来，方法数开始往上长。
放第 3 个 1：放第三个 1：dp[3] 第一次有值（=dp[2]=1），dp[2] 累加到 3，dp[1] 累加到 3。数值排成 [1,3,3,1]，正是杨辉三角的一行。
放第 4 个 1：放第四个 1：dp[4] 终于被点亮（=dp[3]=1），整行变 [1,4,6,4,1]。每一格仍是「左边一格的旧值」叠加上来，杨辉三角继续生长。
放第 5 个 1：放最后一个 1：dp[4] += dp[3]，由 1 累加成 5。整行 [1,5,10,10,5] 是杨辉三角第 5 行。看目标列 dp[4]。
答案 = dp[P]：子集和恰好为 P=4 的选法有 dp[4] = 5 种——对应「让 4 个数取正、1 个取负」的 5 种挑法，这就是答案。
遇到「给每个数选 +/− 凑 target」，一律转成「选子集和恰好为 (sum+target)÷2」的背包计数。一个数学变形，就把看着唬人的符号题打回经典模型。
参考代码（Python）
1s = sum(nums)
2if (s + target) % 2 or s < abs(target): return 0 # P 不是非负整数，无解
3P = (s + target) // 2 # 取正子集的目标和
4dp = [0] * (P + 1); dp[0] = 1 # dp[0]=1：空集凑 0 算一种
5for x in nums:
6 for j in range(P, x - 1, -1): # 0-1: 从大到小，到 x 为止
7 dp[j] += dp[j - x] # 累加：不选 + 选的方法数
8return dp[P]复杂度分析
- 时间复杂度：O(n × P) —— n 个数，每个数扫一遍约 P 个子集和容量格
- 空间复杂度：O(P) —— 只用一行 dp 数组，长度是目标子集和 P
套路模板
记住骨架：dp[0]=1、内层从大到小、dp[j] += dp[j−x]。这类题真正的难点往往是「先把题目变形成子集和」这一步。
1dp = [0] * (W + 1); dp[0] = 1 # 计数初值 1（空集一种）
2for x in items:
3 for j in range(W, x - 1, -1): # 从大到小 = 每个数只用一次
4 dp[j] += dp[j - x] # 累加方案数
5return dp[W]易错点
- 错误写法：不判 (sum+target) 的奇偶和范围 → 正确写法：为奇数或越界先返回 0（P=(sum+target)÷2 必须是非负整数才有意义；和为奇数除不尽、|target| 大于 sum 则无解）
- 错误写法：dp[0] 初值写成 0（沿用布尔版习惯） → 正确写法：计数版 dp[0]=1（空集凑出 0 算一种方法，dp[0]=0 会让所有方法数都乘成 0）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。