目标和 图解题解

这道题到底在问什么

nums

[1, 1, 1, 1, 1]

target

3

输出

5

最优解：一步一步想明白

1. 3最直接的想法：每个数独立选 + 或 −，n 个数就是 2ⁿ 种符号组合，逐一算结果看是否等于 target。数一多就指数爆炸，而且大量子和被重复计算。
2. 4记取 + 的数之和为 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。
3. 5子集和 0~4 的方法数表头是子集和 0 到 4。dp[j] 记「选出的数之和恰好为 j 的方法数」。dp[0]=1（空集就能凑出 0，算一种），其余先为 0。目标看 dp[4]。
4. 6dp[1]=1放第一个 1，内层从大到小扫：dp[1] += dp[0] = 1。意思是「用这一个 1 凑出和 1」有 1 种方法。其余格暂时凑不出，仍是 0。
5. 7dp[0] 不变注意负例：容量 0 这格想装数字 1，j−1 会变成负数，根本装不下。所以循环只扫到 x 为止，dp[0] 永远沿用「这个数不选」的旧值 1。这保证了空集这一种方法不被破坏。
6. 8[1,2,1,0,0]放第二个 1：dp[2] 累加上 dp[1] 得 1，dp[1] 再累加 dp[0] 变成 2。每个 dp[j] 都把「上一个数填好的 dp[j−1]」叠进来，方法数开始往上长。
7. 9[1,3,3,1,0]放第三个 1：dp[3] 第一次有值（=dp[2]=1），dp[2] 累加到 3，dp[1] 累加到 3。数值排成 [1,3,3,1]，正是杨辉三角的一行。
8. 10[1,4,6,4,1]放第四个 1：dp[4] 终于被点亮（=dp[3]=1），整行变 [1,4,6,4,1]。每一格仍是「左边一格的旧值」叠加上来，杨辉三角继续生长。
9. 11dp[4]=5放最后一个 1：dp[4] += dp[3]，由 1 累加成 5。整行 [1,5,10,10,5] 是杨辉三角第 5 行。看目标列 dp[4]。
10. 12dp[4] = 5子集和恰好为 P=4 的选法有 dp[4] = 5 种——对应「让 4 个数取正、1 个取负」的 5 种挑法，这就是答案。
11. 15遇到「给每个数选 +/− 凑 target」，一律转成「选子集和恰好为 (sum+target)÷2」的背包计数。一个数学变形，就把看着唬人的符号题打回经典模型。
12. 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def findTargetSumWays(self, nums, target):
        total = sum(nums)
        if abs(target) > total or (total + target) % 2:
            return 0
        goal = (total + target) // 2
        dp = [0] * (goal + 1)
        dp[0] = 1
        for x in nums:
            for s in range(goal, x - 1, -1):
                dp[s] += dp[s - x]
        return dp[goal]

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

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

dp = [0] * (W + 1); dp[0] = 1           # 计数初值 1（空集一种）
for x in items:
    for j in range(W, x - 1, -1):       # 从大到小 = 每个数只用一次
        dp[j] += dp[j - x]              # 累加方案数
return dp[W]

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

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

复杂度

面试官可能追问