目标和如何转化为 0-1 背包计数问题？

简化版

目标和给每个数加 + 或 -，设正数集合和为 P，负数集合和为 N，有 P - N = target 且 P + N = sum，所以 P = (sum + target) / 2。问题转成从数组中选若干数凑出 P 的方案数，是 0-1 背包计数。

详细版

先检查 sum + target 是否为非负偶数，否则无解。令背包容量 bag = (sum + target) / 2，用 dp[j] 表示凑出和 j 的选择方案数。初始化 dp[0]=1，遍历每个数 num，容量从 bag 倒序到 num，执行 dp[j] += dp[j-num]。

倒序遍历是因为每个数组元素只能选择一次。若数组包含 0，公式仍然有效：0 会让 dp[j] 翻倍，因为 +0 和 -0 是两种符号选择。

完整版教学

一、暴力搜索为什么会爆

每个数字都有 + 和 - 两种选择，n 个数字共有 2^n 种符号方案。

nums = [1,1,1,1,1], target = 3
一种方案：-1 +1 +1 +1 +1 = 3

直接 DFS 可以写，但会重复枚举大量相同和的状态。动态规划的关键是把符号选择转成子集和计数。

二、代数转换怎么来

设被加正号的数字和为 P，被加负号的数字和为 N：

P - N = target
P + N = sum
两式相加：2P = sum + target
P = (sum + target) / 2

因此只要选出一些数作为正号集合，使它们的和为 P，剩下的数自动作为负号集合。

记忆钩子：目标和不是直接背包，先用 P-N 和 P+N 把正号集合求出来。

三、什么时候直接无解

转换后要满足：

条件	原因
`sum + target >= 0`	正数集合和不能为负
`(sum + target) % 2 == 0`	`P` 必须是整数
`abs(target) <= sum`	目标绝对值不能超过总和

例如 sum=5, target=4，sum+target=9 是奇数，不可能分成整数的正号集合。

四、背包状态和转移

定义：

dp[j]：从已经处理过的数字中选若干个，凑出和 j 的方案数

处理 num 时：

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

含义是所有能凑出 j-num 的方案，加上当前数字后都能凑出 j。

五、为什么容量倒序

每个数字只能决定一次符号，不能被重复选择到正号集合里。所以这仍是 0-1 背包，必须倒序。

nums = [1], bag = 2
若正序：dp[1] 更新后又可更新 dp[2]
等价于把一个 1 用了两次

倒序保证 dp[j-num] 来自上一轮。

六、代码模板

int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int x : nums) sum += x;
    if (Math.abs(target) > sum) return 0;
    int total = sum + target;
    if ((total & 1) == 1) return 0;

    int bag = total / 2;
    int[] dp = new int[bag + 1];
    dp[0] = 1;
    for (int num : nums) {
        for (int j = bag; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[bag];
}

当 num=0 时，循环会执行 dp[j] += dp[j]，自然把方案数翻倍，正好对应 +0 和 -0。

七、常见误区与追问

误区：直接把 target 当背包容量。 目标和需要先做正负集合转换，容量是 (sum + target) / 2。
误区：忘记奇偶性判断。 sum + target 为奇数时不存在整数正号集合。
误区：正序遍历容量。 每个数只能选择一次，正序会重复使用。
追问：数组里有 0 怎么办？ 0 会让当前所有方案数翻倍，因为 +0 和 -0 都合法。
追问：复杂度是多少？ 时间 O(n * bag)，空间 O(bag)。
追问：能用记忆化 DFS 吗？ 可以，状态是 (index, currentSum)，但背包转换更经典。

八、加强记忆

目标和的突破口是代数转换：正号集合和减负号集合和等于 target，二者相加等于 sum，所以正号集合和是 (sum + target) / 2。转成子集和后，它就是 0-1 背包计数，dp[j] 表示凑出 j 的方案数，倒序保证每个数只用一次。遇到 0 不要特判漏掉，它会自然让方案翻倍，这是这题很好的边界校验点。

简化版

详细版