LeetCode 494. 目标和
目录
题目描述
✅ 494. 目标和
题意分析
要的是方案数而不是某一种方案：每个数字前必须放一个
+或-，两种符号都要放满，问有多少种放法能让表达式的值等于target。
约束里有三个关键信号。第一，数组元素非负（0 <= nums[i] <= 1000），这让「按符号分成两个子集」之后两边都是非负数，容量的概念才立得住。第二，元素总和不超过 1000、长度不超过 20，说明按「和」做状态是够用的，而 $2^{20}$ 的暴力枚举虽然勉强能过但显然不是想考的。第三，target可以是负数（-1000 <= target <= 1000），推导时不能默认它非负。
边界要注意两处：数组里可以有0，+0与-0是两种不同的放法，会让方案数成倍增加，因此不能把0当成「无关元素」跳过；target的绝对值一旦超过总和，无论怎么放都够不着，答案是0。
解法：转化为 0/1 背包计数
核心思路
直接为每个数字枚举正负号需要
\[P-N=target,\qquad P+N=sum\]O(2^n)。由于数组元素非负，可以把下标分成“取正号”和“取负号”两个子集，分别记元素和为P、N：两式相加得到：
\[P=\frac{sum+target}{2}\]因此，每种符号方案都唯一对应一个“元素和为
P的下标子集”，反过来也成立，原问题就转成 0/1 背包的方案计数。这里按下标选元素，所以数值相同的元素仍是不同选择；0也不会丢失，选或不选分别对应+0和-0。转换前必须满足两个条件：
|target| <= sum，否则正负号能得到的范围无法覆盖目标；sum + target为偶数，否则P不是整数。定义
dp[j]为处理完当前前缀后，元素和恰好为j的子集个数。初始dp[0] = 1，表示空集。处理num时执行dp[j] += dp[j-num]：右侧分别对应“不选”和“选当前元素”的方案。容量必须从大到小更新，确保dp[j-num]仍是处理当前元素之前的值，当前下标只会被使用一次。按上述定义归纳：每轮更新后，
dp[j]恰好包含当前数字不选与选两类互斥方案，且覆盖全部选择，因此计数无重无漏。最终dp[P]就是目标和方案数。
解题步骤
- 求数组总和
sum。- 若
|target| > sum或sum + target为奇数，直接返回 0。- 计算背包容量
P = (sum + target) / 2，创建dp[0..P]并令dp[0] = 1。- 依次处理每个数字；容量
j从P倒序到num，累加dp[j-num]。- 返回
dp[P]。以
nums = [1,1,1,1,1]、target = 3为例，sum = 5，所以P = 4。问题变成从 5 个位置中选出和为 4 的子集，也就是选 4 个1，共有 5 种。若数字是0，更新dp[j] += dp[j]会把已有方案数翻倍，恰好表示+0与-0两种选择。
代码实现
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (Math.abs(target) > sum || (sum + target) % 2 != 0) {
return 0;
}
int capacity = (sum + target) / 2;
int[] dp = new int[capacity + 1];
dp[0] = 1;
for (int num : nums) {
for (int j = capacity; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[capacity];
}
}
func findTargetSumWays(nums []int, target int) int {
sum := 0
for _, num := range nums {
sum += num
}
if target > sum || target < -sum || (sum+target)%2 != 0 {
return 0
}
capacity := (sum + target) / 2
dp := make([]int, capacity+1)
dp[0] = 1
for _, num := range nums {
for j := capacity; j >= num; j-- {
dp[j] += dp[j-num]
}
}
return dp[capacity]
}
复杂度分析
- 时间复杂度：
O(nP)，其中P = (sum + target) / 2；最坏可写为O(n · sum)。- 空间复杂度：
O(P)，二维背包状态被压缩成一维数组。
关键点总结
- 先写出
P-N=target与P+N=sum，再推出子集和容量，不要直接背公式。- 子集和必须同时通过范围和奇偶校验。
dp[j]统计的是“和恰好为j的方案数”，所以初值是dp[0] = 1，转移用加法。- 一维 0/1 背包必须倒序更新，保证每个数组下标只选一次。
0不需要特判；当num == 0时状态自然翻倍，正确计入两种符号。
易错点总结
- 漏判
|target| > sum：nums = [1]、target = -3时，sum + target虽为偶数，但容量为负，创建数组会失败。- 整除前不判奇偶：
nums = [1,2]、target = 2时sum + target = 5，整数除法会错误地把容量截成 2，本应返回 0。- 容量正序更新：
nums = [1,2]、target = 3时会在同一轮重复使用第一个1，把正确答案 1 算成 2。- 把
dp[0]设为 0：计数没有起点，之后所有状态都会保持为 0。- 跳过数组中的 0：
nums = [0,1]、target = 1有+0+1、-0+1两种方案，跳过 0 只会得到 1。- 只判断
target > sum：较小的负目标同样不可达，应判断绝对值或同时检查上下界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 416. 分割等和子集 | 中等 | 同样折成子集和，但求可行性而非方案数 |
| 474. 一和零 | 中等 | 两个维度的容量，求最多选取件数 |
| 879. 盈利计划 | 困难 | 二维容量下计数，且利润维是「至少」型 |
| 1049. 最后一块石头的重量 II | 中等 | 同样按正负分组，但求两组差值的最小值 |
| LCR 101. 分割等和子集 | 简单 | 等和分割换编号，容量固定为 sum / 2
|
| LCR 102. 目标和 | 中等 | 本题换编号，推导与实现完全一致 |