LeetCode LCR 102. 目标和
题目描述
题意分析
给每个数组位置添加一个正号或负号，统计表达式结果等于
target的方案数。提示允许元素为 0；相同数值位于不同位置时，仍是不同的赋号选择。设数组总和为 $S$，正号部分的和为 $P$，负号部分的绝对值之和为 $N$。由 $P-N=target$、$P+N=S$，得到 $P=(S+target)/2$。选出哪些位置放进正号子集后，其余位置的负号也随之确定，因此可以改为统计和为 $P$ 的子集数量。
解法：转成正号集合的 01 背包计数
核心思路
[!blue]
先保证 $P$ 是合法的非负整数。代码用
s = sum + target，若它为负或为奇数就返回 0；再令p = s / 2，若p > sum也无解。这几项检查同时排除了目标在总和范围之外和奇偶不匹配的情况。定义
dp[j]为使用已处理位置、选出和为j的子集数量。初始dp[0] = 1，代表一个元素都不选的唯一空集，其余计数为 0。处理元素x时，不选它的方案已经保存在dp[j]中；选它的方案则是在旧的和为j - x的每个子集上加入当前位置，所以执行dp[j] += dp[j - x]。每个位置最多选择一次，因此容量倒序。对正数
x，j - x比j小，尚未在本轮更新，保证前驱方案没有使用当前位置。即使多个位置的值相同，也要逐个处理，因为选取的位置不同对应不同表达式。当
x = 0时，转移变为dp[j] += dp[j]，将已有方案恰好翻倍：当前零可以属于正号子集，也可以属于负号部分。两种表达式数值相同，但按题意都应计数。循环必须包含j = 0，这样总和为 0 的输入也能正确统计所有赋号方式。最后返回
dp[p]。所有被统计的子集都对应唯一的正负号分配，反过来每个合法表达式也会落入其中，因此没有遗漏或重复。
解题步骤
- 求总和，计算
s = sum + target，排除负数和奇数。- 令
p = s / 2，若p > sum，返回 0。- 创建计数数组并设置
dp[0] = 1。- 逐个处理
x，让j从p递减到x，执行计数累加。- 返回
dp[p]。
代码实现
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(P+1))$，其中 $n$ 为元素个数、$P=(S+target)/2$；保留加一项也覆盖 $P=0$ 时逐个处理零的情况。
- 空间复杂度：$O(P+1)$，保存 0 到正号目标和的计数。
关键点总结
[!green]
- 子集按数组位置区分，不能将重复值去重。
- 计数初值为一个空方案，转移用加法；不能用布尔可达状态代替。
- 每个零都会将当前计数翻倍，不应过滤零或跳过容量 0。
- 数组最多 20 个元素，赋号方案总数不超过 $2^{20}$，现有整数计数足够。
易错点总结
[!yellow]
- 未检查范围与奇偶就建立背包，可能得到无效或错误的目标容量。
- 正序更新会重复选择当前正数，无法对应每个位置只赋一个符号。
- 将
dp[0]设为 0 会失去空方案，所有计数都无法启动。- 把零的正负号合并成一种，会少计不同的表达式。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 416. 分割等和子集 | 中等 | 同样将问题转成子集和，本题需要方案数量而不是可达布尔值。 |
| 518. 零钱兑换 II | 中等 | 同样做容量计数，原题硬币可重复使用，本题每个下标只选择一次，更新方向不同。 |