目标和 图解题解

目标和这道题在问什么

给数组 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 的两种添法，不需要任何特判。

Python

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]

C++

int findTargetSumWays(vector<int>& nums, int target){
    int s = 0; for(int x : nums) s += x;
    if((s + target) % 2 || s < abs(target)) return 0;
    int P = (s + target) / 2;
    vector<int> dp(P + 1, 0); dp[0] = 1;
    for(int x : nums)
        for(int w = P; w >= x; --w)
            dp[w] += dp[w - x];
    return dp[P];
}

Java

public int findTargetSumWays(int[] nums, int target){
    int s = 0; for(int x : nums) s += x;
    if((s + target) % 2 != 0 || s < Math.abs(target)) return 0;
    int P = (s + target) / 2;
    int[] dp = new int[P + 1]; dp[0] = 1;
    for(int x : nums)
        for(int w = P; w >= x; w--)
            dp[w] += dp[w - x];
    return dp[P];
}