LC494.目标和

题目描述

给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 示例 1： 输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3 示例 2： 输入：nums = [1], target = 1 输出：1 提示： 1 <= nums.length <= 20 0 <= nums[i] <= 1000 0 <= sum(nums[i]) <= 1000 -1000 <= target <= 1000

题目解析

题目在说什么

想象你手里有一堆数字，比如 [1, 1, 1, 1, 1]，每个数字前面你都可以选择加一个 + 号或者 - 号，然后把这些带符号的数字加起来，得到一个最终结果。题目问：有多少种不同的加号/减号选择方式，能让最终结果等于给定的 target（比如 3）？

比如示例里，有 5 种方法能让结果等于 3，其中一种就是 -1 + 1 + 1 + 1 + 1 = 3。你可能会想：这不就是每个数字要么加要么减嘛，像在玩一个“正负选择”的游戏。

思路是怎么来的

第一步：把“正负选择”变成“选不选”的问题

每个数字前面加 + 还是 -，其实相当于把数字分成两堆：

• 一堆是加号的数字（我们叫它 A 堆）
• 一堆是减号的数字（我们叫它 B 堆）

整个表达式的结果就是：A 堆的和减去 B 堆的和 = target。

第二步：用数学公式简化

设所有数字的总和是 sum，A 堆的和是 sumA，B 堆的和是 sumB。那么：

• sumA + sumB = sum（因为所有数字都分到两堆里了）
• sumA - sumB = target（因为表达式结果要等于 target）

把这两个等式加起来：2 * sumA = sum + target，所以 sumA = (sum + target) / 2。

关键发现：我们不需要关心每个数字是加还是减，只需要知道：从数组里选出一堆数字（A 堆），让它们的和恰好等于 (sum + target) / 2，有多少种选法？因为一旦 A 堆确定了，剩下的自然就是 B 堆，符号也就确定了。

第三步：这个新问题像什么？

这就变成了一个经典的“背包问题”：你有一个背包，容量是 bagSize = (sum + target) / 2，每个数字是一个物品，每个物品只能选一次（因为每个数字只能被分配一次），问有多少种方式恰好把背包装满。

比如 nums = [1, 1, 1, 1, 1]，target = 3，总和 sum = 5，那么 bagSize = (5 + 3) / 2 = 4。问题就变成：从 5 个 1 里选几个 1，让它们的和恰好是 4，有多少种选法？答案是 5 种（选任意 4 个 1 就行），正好对应了示例。

第四步：注意特殊情况

• 如果 (sum + target) 是奇数，那 bagSize 就不是整数，不可能有解，直接返回 0。
• 如果 bagSize 是负数（比如 target 太小），也不可能，返回 0。

代码逐步拆解

我们来看参考代码，一步一步拆开讲。

1. 计算总和和背包容量

int sum = 0;
for (int num : nums) {
    sum += num;
}
int bagSize = (target + sum) / 2;

这里先算出所有数字的总和 sum，然后算出背包容量 bagSize。注意：bagSize 是我们要凑的目标和。

2. 处理特殊情况

if (bagSize < 0) return 0;
if ((target + sum) % 2 == 1) return 0;

• 如果 bagSize 是负数，说明 target 太小，根本不可能，直接返回 0。
• 如果 (target + sum) 是奇数，说明 bagSize 不是整数，也不可能，返回 0。

3. 定义 DP 数组并初始化

int[][] dp = new int[nums.length + 1][bagSize + 1];
for (int i = 0; i <= nums.length; i++) {
    dp[i][0] = 1;
}

• dp[i][j] 表示：从前 i 个数字中选，凑出和为 j 的方法数。
• 为什么 dp[i][0] = 1？因为不管有多少个数字，不选任何数字就能得到和为 0，这是一种方法。比如前 0 个数字（没有数字），和为 0 只有一种方法（什么都不选）；前 1 个数字，和为 0 也只有一种方法（不选这个数字）。

4. 填充 DP 表格

for (int i = 1; i <= nums.length; i++) {
    for (int j = 0; j <= bagSize; j++) {
        if (j < nums[i - 1]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
        }
    }
}

这里 i 从 1 开始，对应数组的第 1 个数字（下标 0）。nums[i - 1] 就是当前数字。