LeetCode LCR 102. 目标和

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 102. 目标和

题意分析

给一个非负整数数组 nums，要求给每一个元素前面添上 + 或 -，把它们连成一个表达式，问有多少种添号方式使表达式的值等于 target。注意是「多少种」——要的是方案数，不是判断可行、也不是求最优值。

「每个元素必须选号，且只选一次」意味着这是一次对每个元素的二元决策，天然是 0-1 结构。数组长度上限只有 20，$2^{20} \approx 10^6$，暴力枚举其实能过；但元素和的上限也只有 1000，这个更紧的数值约束提示了一条时间上限更低、也更能体现功底的路。

关键的题意转化在于：把带号的元素分成两堆，取正号的一堆和为 $P$，取负号的一堆（取绝对值后）和为 $N$。那么题意给出两个方程：$P - N = target$，而 $P + N = S$（$S$ 为数组总和，因为每个元素必被分入其中一堆）。两式相加得 $P = (S + target) / 2$。于是「凑出 target」被翻译成了「选出一个和恰好为 $(S + target)/2$ 的子集」，负号那堆自动确定，不需要单独枚举。

边界随之而来：$S + target$ 必须是非负偶数，否则 $P$ 不是合法的非负整数，答案为 0；target 的绝对值超过 $S$ 时同样无解。另外 nums 允许出现 0，而 0 前面加正号还是负号得到的是两个不同的表达式，计数时必须把它们算成两种方案，这是本题最容易被忽略的细节。

解法：动态规划递推

核心思路

暴力是对每个位置枚举 + 或 -，递归到底再判断和是否等于 target，时间 $O(2^n)$。$n = 20$ 时是一百万条路径，勉强能跑，但一旦长度放宽到 40 就彻底崩溃，而且它做了大量重复劳动。

瓶颈同样在于「分支等价」：走到第 $i$ 个位置时，前面那些符号具体怎么选并不重要，只有当前累计的和影响后续能否成功。把累计和相同的分支合并，指数树就塌成了一张按和索引的计数表。

再叠加上题意分析里的那步代数化简，问题彻底变成一个标准形态：从 nums 中选出若干个数，使其和恰为 $P = (S + target)/2$，问有多少种选法。

于是状态定义为：dp[j] = 在已考察的前若干个元素中，和恰好为 j 的子集的个数。数组长度 P + 1。

初始状态 dp[0] = 1：什么都不选，和为 0，这是唯一一种「空方案」。注意它是 1 而不是 0——计数型 DP 的起点是「一种方案」，与可达性型 DP 用 true 起步一一对应。

转移方程：考察元素 x 时，dp[j] += dp[j - x]。含义是「和为 j 且用了 x 的方案数」等于「和为 j - x 且没用过 x 的方案数」，把它累加到原有的「不用 x 就能凑出 j」的方案数上。

不变量：处理元素 x 的整个内层循环期间，读到的 dp[j - x] 必须是尚未把 x 计入的那一版，否则 x 会被重复使用，方案数偏大。维持这条不变量的手段是容量倒序遍历。

最终答案是 dp[P]。

解题步骤

累加求出总和 sum。为什么：后续所有推导都依赖 $S$，而且 sum 同时充当「target 是否越界」的判据。

计算 s = sum + target，若 s < 0 或 s 为奇数则直接返回 0。为什么：$P = s/2$ 必须是非负整数，s 为负说明 target 比 $-S$ 还小，s 为奇说明正负两堆的和的奇偶性对不上，两种情况都一个方案都没有。

令 p = s / 2，若 p > sum 返回 0。为什么：正号那堆的和不可能超过全部元素之和，这一条挡住了 target > sum 的越界输入，也顺带保证了后面开数组时下标安全。

开长度 p + 1 的整型数组 dp，置 dp[0] = 1。为什么长度是 p + 1：下标要覆盖到 p 本身。为什么初值是 1：空集是凑出和 0 的唯一方案，所有计数都从它生长出来。

外层遍历元素 x，内层从 j = p 递减到 j = x，执行 dp[j] += dp[j - x]。为什么外层是元素：保证每个元素只被决策一次。为什么倒序：维持上面那条不变量，让 dp[j - x] 停留在旧值。为什么下界是 x：j < x 的位置装不下 x，本轮不受影响，且 j - x 会越界。

返回 dp[p]。为什么：它的含义正是「和为 p 的子集个数」，每一个这样的子集唯一对应一种合法的加号方案。

以 nums = [1, 1, 1, 1, 1]、target = 3 走一遍。sum = 5，s = 5 + 3 = 8，是非负偶数，p = 4，且 4 ≤ 5 合法。dp 长度 5，初值 [1, 0, 0, 0, 0]。

处理第 1 个 1：j 从 4 递减到 1，只有 j = 1 时 dp[0] = 1 有贡献，得到 [1, 1, 0, 0, 0]。

处理第 2 个 1：倒序更新，j = 2 时 dp[2] += dp[1] 得 1，j = 1 时 dp[1] += dp[0] 得 2。dp[1] = 2 的含义是「从前两个 1 里任挑一个凑出和 1」，确实有两种选法。此轮结束得到 [1, 2, 1, 0, 0]。

处理第 3 个 1：j = 3 得 dp[3] += dp[2] = 1；j = 2 得 dp[2] += dp[1] = 1 + 2 = 3；j = 1 得 dp[1] += dp[0] = 3。数组为 [1, 3, 3, 1, 0]，正是杨辉三角第三行。

处理第 4 个 1：得到 [1, 4, 6, 4, 1]。

处理第 5 个 1：得到 [1, 5, 10, 10, 5]。

返回 dp[4] = 5，与 $\binom{5}{4} = 5$ 一致：从五个 1 中挑四个加正号、剩下一个加负号，$4 - 1 = 3$，恰好命中 target，共 5 种。

再看含 0 的用例 nums = [0, 1]、target = 1。sum = 1，s = 2，p = 1，dp = [1, 0]。处理 x = 0 时内层 j 从 1 递减到 0，dp[1] += dp[1]（仍是 0）、dp[0] += dp[0] 变成 2——这一步把「0 取正号」和「0 取负号」两种写法都记了下来。再处理 x = 1：j = 1 时 dp[1] += dp[0] = 2。返回 2，对应 +0+1 与 -0+1，与题意要求的「表达式数目」一致。

代码实现

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }

        // 正号那堆的和 p 满足 p - (sum - p) = target，即 2p = sum + target。
        int s = sum + target;
        if (s < 0 || s % 2 != 0) {
            return 0;
        }
        int p = s / 2;
        if (p > sum) {
            return 0;
        }

        int[] dp = new int[p + 1];
        dp[0] = 1;

        for (int x : nums) {
            // 倒序保证 dp[j - x] 尚未计入本轮的 x。
            for (int j = p; j >= x; --j) {
                dp[j] += dp[j - x];
            }
        }

        return dp[p];
    }
}

func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, x := range nums {
        sum += x
    }

    // 正号那堆的和 p 满足 p - (sum - p) = target，即 2p = sum + target。
    s := sum + target
    if s < 0 || s%2 != 0 {
        return 0
    }
    p := s / 2
    if p > sum {
        return 0
    }

    dp := make([]int, p+1)
    dp[0] = 1

    for _, x := range nums {
        // 倒序保证 dp[j-x] 尚未计入本轮的 x。
        for j := p; j >= x; j-- {
            dp[j] += dp[j-x]
        }
    }

    return dp[p]
}

复杂度分析

时间复杂度：$O(n \cdot S)$，其中 $n$ 是元素个数、$S$ 是数组总和。凭什么：外层扫 $n$ 个元素，内层最多扫 $P + 1 \le S + 1$ 个容量，循环体只有一次加法。题目保证 $S \le 1000$、$n \le 20$，规模约 $2 \times 10^4$。

空间复杂度：$O(S)$。凭什么：只保留一维长度为 $P + 1$ 的计数数组，元素维被滚动掉了；相比按「和的偏移量」开二维表的写法，空间从 $O(nS)$ 降到 $O(S)$。

关键点总结

「每个元素带正负号求方案数」的标准套路是列出 $P - N = target$、$P + N = S$ 两式相消，把双向决策压成单向的子集和问题——这一步代数变换本身就是考点。

计数型 DP 的起点是 dp[0] = 1 而不是 0，转移用 += 而不是 ||；把它和可达性型 DP（dp[0] = true、用 ||）放在一起记，两者是同一骨架的两种取值语义。

0-1 背包一维写法必须倒序遍历容量，能解释「倒序让 dp[j-x] 保持上一轮的值」比背下口诀更重要。

无解的判定要落在代数条件上（s < 0、s 为奇、p > sum），而不是靠试算兜底，这样边界既全又互不重叠。

元素允许为 0 时，0 的两种符号是两种方案，DP 里 dp[j] += dp[j] 自然翻倍，不需要任何特殊处理——面试中主动点出这一点会显得对状态语义理解到位。

面试视角：先给 $O(2^n)$ 回溯并说明它的重复子问题，再做代数化简，最后给出 $O(nS)$ 的背包，完整展示「暴力 → 瓶颈 → 转化」的链条。

易错点总结

忘记判 s 的奇偶：nums = [1, 2]、target = 2 时 s = 5，若直接整除得 p = 2，会算出 1 种方案，而真实答案是 0。

忘记判 s < 0：nums = [1]、target = -5 时 s = -4，p = -2，Java 用负长度 new int[-1] 抛 NegativeArraySizeException，Go 的 make 直接 panic。

忘记判 p > sum：nums = [1]、target = 100 时 s = 101 为奇数恰好被挡住，但 target = 101 时 s = 102、p = 51，数组开得下却永远填不满，虽然返回 0 但白白多开了内存；输入规模更大时这一条能直接省掉整轮 DP。

dp[0] 初始化成 0：整张表恒为 0，nums = [1, 1, 1, 1, 1]、target = 3 会返回 0 而不是 5。

内层容量正序遍历：nums = [1, 2]、target = 3（p = 3）时，处理 x = 1 会依次把 dp[1]、dp[2]、dp[3] 都填成 1，相当于 1 用了三次，最终返回 2 而正确答案是 1。

内层下界写成 j >= 0：x = 2、j = 1 时访问 dp[-1]，Java 抛越界异常、Go panic。

对含 0 的输入先把 0 过滤掉：nums = [0, 1]、target = 1 会返回 1，而正确答案是 2，因为 +0 与 -0 是两个不同的表达式。

把 += 写成 =：nums = [1, 1]、target = 0（p = 1）时 dp[1] 会被后一个 1 覆盖成 1，返回 1 而正确答案是 2。

用 dp[j] += dp[j - x] 但外层遍历容量、内层遍历元素：nums = [1, 2]、target = 3 会把同一元素反复计入，方案数偏大。

返回 dp[sum] 或 dp[target]：状态数组的下标语义是「正号堆的和」，只有 dp[p] 才对应题目要求的表达式数目。

相似题目

题目	难度	考察点
494. 目标和	中等	与本题同题，可直接套用同一份代码
416. 分割等和子集	中等	目标固定为 `sum/2`，且只问可行性，计数表退化为布尔可达表
1049. 最后一块石头的重量 II	中等	同样是正负分堆，但求的是两堆差的最小值，需要遍历可达和取最优
474. 一和零	中等	容量是二维的（0 的个数与 1 的个数），两维都要倒序
879. 盈利计划	困难	计数型 0-1 背包，利润维是「至少」约束，下标需要对 0 做截断
LCR 101. 分割等和子集	简单	与 416 同题，是本题去掉计数、只留可达性的简化版
1155. 掷骰子等于目标和的方法数	中等	每轮必须从 1..k 中恰好选一个，是「分组背包」而非选与不选的二元决策