LeetCode 494. 目标和

题目核心

给你一个整数数组 nums 和一个整数 target。

向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数，可以构造一个表达式：

• 例如，nums = [2, 1]，可以在 2 之前加 '+'，在 1 之前加 '-'，得到表达式 "+2-1"。

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

例如：

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

解题思考过程

第一步：理解问题

每个数前面要么是 + 要么是 -，没有其他选项。所以对 n 个数，总共有 2ⁿ 种组合方式。问的是其中多少种组合运算结果等于 target。

第二步：最朴素的 DFS 暴力

对每个位置两种选择（加正/加负），递归枚举所有情况，选完 n 个数时判断和是否等于 target。

时间复杂度：O(2ⁿ)
空间复杂度：O(n) 递归栈

如果 n 很小（比如 ≤ 20）可以过，但 LeetCode 494 中 n 最大到 20，暴力容易接近超时边界；如果 n 更大就必须优化。

第三步：问题转换——把加减变成子集和

这是这道题最精妙的一步，思路如下：

假设最终加了 '+' 的那些数组成集合 P，加了 '-' 的那些数组成集合 N。

那么题目要求就是：

sum(P) - sum(N) = target   ……①

而整个数组的总和 S = sum(P) + sum(N) ……②

把 ① + ②：

sum(P) - sum(N) + sum(P) + sum(N) = target + S
2 · sum(P) = target + S
sum(P) = (target + S) / 2

于是问题从"给每个数选 + 或 - 使结果等于 target"，转换成了一个纯子集问题：

从 nums 中选若干个数放进 P，让它们的和等于 (S + target) / 2。有多少种选法？

这就完全是经典的0-1 背包求方案数了。

第四步：转换后的预处理

• 如果 (S + target) 是奇数 → 除以 2 不是整数 → 不可能有解，直接返回 0。
• 如果 (S + target) < 0 → 不可能（和是正数，target 加 S 小于 0 说明目标根本达不到），返回 0。

第五步：DFS + 记忆化

对于"选/不选当前元素，求凑成 target 的方案数"这个子集问题，可以用 DFS + 记忆化：

• dfs(index, sum)：表示"从 nums[index...] 开始选，要凑出 sum 的方案数"。
• 状态转移：
  • 不选 nums[index]：dfs(index + 1, sum)
  • 选 nums[index]（只有 sum >= nums[index] 时可选）：dfs(index + 1, sum - nums[index])
• 用二维数组 mem[index][sum] 缓存结果，避免重复计算。

第六步：动态规划（0-1 背包）

进一步可以写成迭代 DP：

• dp[j]：凑成和为 j 的方案数。
• 初始：dp[0] = 1（凑成和为 0 的方案数是 1：什么都不选）。
• 对每个数 num，倒序遍历 j 从 P 到 num：
  • dp[j] += dp[j - num]（不选的情况已经在原来的 dp[j] 里了，加上选的情况即可）。

时间复杂度：O(n * P)
空间复杂度：O(P)（滚动一维数组）

解法一：纯 DFS 暴力（初始版本）

每个数要么作正，要么作负，枚举所有 2ⁿ 种情况：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  /*
  也就是说我们有多少种方式组合成目标，但是组合的方式只有加减方式
  我们先用dfs加记忆
  */

  let ans = 0;
  let start = 0;
  const dfs = (nums, index, target) => {
    if (index === nums.length) {
      if (target === 0) {
        ans++;
      }
      return;
    }
    // 作为正
    dfs(nums, index + 1, target + nums[index]);
    // 作为负
    dfs(nums, index + 1, target - nums[index]);
  };

  dfs(nums, 0, target);
  return ans;
};

代码逐行解释

let ans = 0;

全局计数器，记录合法表达式的数量。

const dfs = (nums, index, target) => {

递归参数：

• index：当前处理到第几个数。
• target：剩余的目标值（初始传入的是题目给定的 target，每加/减一个数后 target 变化）。

注意这里 target 是"还差多少"——不是已经累计的和，这样判断终止时更方便：如果选完所有数后 target 被"恰好抵消为 0"，说明表达式和等于原目标。

if (index === nums.length) {
  if (target === 0) ans++;
  return;
}

所有数都选过了：

• 如果此时 target === 0 → 表达式结果刚好等于目标，ans +1。
• 否则什么都不做，返回。

dfs(nums, index + 1, target + nums[index]);   // 作为正
dfs(nums, index + 1, target - nums[index]);   // 作为负

对当前数两种选项：

• 当成正数：相当于要让剩下的数凑出 target + nums[index]（因为表达式里 +nums[index]，所以剩下的部分需要再把这个数"加回来"凑成 target）。
• 当成负数：相当于要让剩下的数凑出 target - nums[index]。

执行过程示例

nums = [1, 1], target = 0：

dfs(0, 0):
  dfs(1, 0+1=1):            // 第 0 个 1 取 +
    dfs(2, 1+1=2):         // 第 1 个 1 取 + → index=2，target=2≠0
    dfs(2, 1-1=0):         // 第 1 个 1 取 - → target=0，ans=1
  dfs(1, 0-1=-1):           // 第 0 个 1 取 -
    dfs(2, -1+1=0):        // 第 1 个 1 取 + → target=0，ans=2
    dfs(2, -1-1=-2):       // target=-2≠0

最终 ans = 2。对应：+1-1=0 和 -1+1=0。

复杂度

• 时间复杂度：O(2ⁿ)。每个节点分叉两次，完全二叉树结构。
• 空间复杂度：O(n) 递归栈深度。

局限

n = 20 时 2²⁰ ≈ 100 万，马马虎虎能过；但如果 n = 30 就超过 10 亿，会超时。需要优化。

解法二：记忆化 DFS（子集和转换）

关键点：先把问题转化为"选出和为 P = (S + target) / 2 的子集有多少种"，再用 DFS + 记忆化。

注意：贴的版本里有几个笔误（x/sum/n 未定义、赋值循环误改 target），下面是修正后的版本。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  /*
  也就是说我们有多少种方式组合成目标，但是组合的方式只有加减方式。
  我们先用 dfs 加记忆，但关键是在于转换问题，把组合的方式转换成另外一个问题：
    P - N = target
    P + N = S
    2P = S + target
    P  = (S + target) / 2
  也就是说有多少种组合方式加起来等于 P？
  哪些数字应该被选进 P，使它们的和等于 (S + target) / 2？
  */

  const n = nums.length;
  let S = 0;
  for (let i = 0; i < n; i++) {
    S += nums[i];
  }
  if ((S + target) < 0 || (S + target) % 2 !== 0) {
    return 0;
  }
  const P = (S + target) / 2;

  // mem[index][sum] = 从 index 开始，凑出 sum 的方案数
  const mem = Array.from({ length: n + 1 }, () => new Array(P + 1).fill(-1));

  const dfs = (index, sum) => {
    if (mem[index][sum] !== -1) {
      return mem[index][sum];
    }
    if (index === n) {
      return sum === 0 ? 1 : 0;
    }

    // 不选 nums[index]，无论如何都可以不选
    let res = dfs(index + 1, sum);
    // 选 nums[index]：只有剩余 sum 够 nums[index] 才允许选
    if (sum >= nums[index]) {
      res += dfs(index + 1, sum - nums[index]);
    }

    mem[index][sum] = res;
    return res;
  };

  return dfs(0, P);
};

代码逐行解释

1. 问题转换

let S = 0;
for (let i = 0; i < n; i++) S += nums[i];
if ((S + target) < 0 || (S + target) % 2 !== 0) return 0;
const P = (S + target) / 2;

由 P - N = target 和 P + N = S 推出 P = (S + target) / 2：

• (S + target) 是奇数 → P 不是整数 → 无解。
• (S + target) < 0 → P 为负数，不可能选出来 → 无解。

原版本错误点：它用的是 target += nums[i] 而不是 S += nums[i]，直接把 target 改了，逻辑就乱了——后面再除以 2 的也是改坏的值。修正为单独的 S 变量保存总和，不动 target。

2. 记忆数组

const mem = Array.from({ length: n + 1 }, () => new Array(P + 1).fill(-1));

mem[index][sum]：从第 index 个数开始，凑出和为 sum 的方案数。初始用 -1 标记"还没算过"（因为方案数可能是 0，不能用 0 当标记）。

原版本错误点：

• if (target < nums[x]) 里的 x 是未定义变量 → 应为 index；
• mem[x][sum] 的 x 和 sum 同样是未定义 → 应为 mem[index][target] 或改语义为 mem[index][sum]。
• mem 直接硬编码 1010×1010 有可能不够（比如 P 很大的时候），更稳是 (n+1) × (P+1)。

3. 记忆命中直接返回

if (mem[index][sum] !== -1) return mem[index][sum];

如果这个状态已经算过，直接拿缓存结果。

4. 递归终点

if (index === n) return sum === 0 ? 1 : 0;

所有数都考虑完了：

• 要凑的 sum 刚好是 0 → 找到一种方案（啥都不选/选的都不选刚好凑 0），返回 1。
• 否则返回 0。

5. 不选当前元素

let res = dfs(index + 1, sum);

无论 nums[index] 有多大，不选它都是合法的，所以先加这部分贡献。

6. 选当前元素（条件许可时）

if (sum >= nums[index]) {
  res += dfs(index + 1, sum - nums[index]);
}

只有当 sum >= nums[index] 时，才可能把它选进 P，否则凑不出（目标和会变成负数）。选它之后，剩下的 index+1... 部分要凑 sum - nums[index]。

原版本错误点：target < nums[x] 的分支里只写了"不选"的情况，但写法是 if (target < nums[x]) { 只赋值不选 } return，这样当 target >= nums[x] 时又加了两种分支，语义是对的，但变量名都是错的（x/sum）。我统一写成"先算不选，条件满足再加选"，更清晰。

7. 缓存结果并返回

mem[index][sum] = res;
return res;

无论走哪条分支，把结果存进 mem，下一次再遇到同一个 (index, sum) 就不用再算了。

执行过程示例

nums = [1, 1, 1, 1, 1], target = 3

• S = 5, S + target = 8, P = 4。问题转成"从 5 个 1 里选出若干个，和为 4 的方案数"。

"选 4 个 1"共 5 种（C(5,4)=5），和答案一致。DFS 过程：

dfs(0, 4):
  不选 nums[0]=1 → dfs(1, 4) → "后4个1里选和为4"=1 种（全选后 4 个）
  选 nums[0]=1   → dfs(1, 3) → "后4个1里选和为3"=4 种
  合计 1 + 4 = 5 ✓

复杂度

• 时间复杂度：O(n·P)。每个 (index, sum) 状态只算一次，最多 n·P 个。
• 空间复杂度：O(n·P)（mem 数组） + O(n)（递归栈）。

解法三：动态规划（0-1 背包一维数组）

从"子集和凑成 P 的方案数"直接写 0-1 背包，是三种写法里时间和空间最标准的版本：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
  let S = 0;
  for (const num of nums) S += num;
  if ((S + target) < 0 || (S + target) % 2 !== 0) return 0;
  const P = (S + target) / 2;

  // dp[j]：凑成和为 j 的方案数
  const dp = new Array(P + 1).fill(0);
  dp[0] = 1;   // 凑成 0 的方案数 = 1（什么都不选）

  for (const num of nums) {
    // 倒序：每个数只用一次（0-1 背包）
    for (let j = P; j >= num; j--) {
      dp[j] += dp[j - num];
    }
  }

  return dp[P];
};

代码逐行解释

const dp = new Array(P + 1).fill(0);
dp[0] = 1;

dp[j] 含义：使用已经遍历过的那些数，能凑成和为 j 的方案数。
初始 dp[0] = 1：一个数都不选时，凑出和为 0 有且只有 1 种方案（空集）。

for (const num of nums) {
  for (let j = P; j >= num; j--) {
    dp[j] += dp[j - num];
  }
}

对每个数 num：

• 倒序遍历 j 从 P 往下到 num，这是0-1 背包的典型写法——防止同一轮里 num 被重复使用（如果正序就变成"多重背包"，数可以被选多次）。
• dp[j] += dp[j - num]：在之前"不选 num 的方案数 dp[j]"基础上，加上"选了 num 后凑出 j"的方案数 dp[j - num]。

注意这里 += 左边的 dp[j] 本身已经是"不选 num"的情况（因为上一轮已经处理完它），所以不需要再加一次。

return dp[P];

处理完所有数后，dp[P] 就是"从所有数中选出和为 P 的子集的方案数"，也就等于原题答案。

执行过程示例

nums = [1, 1, 1, 1, 1], P = 4：

初始：dp = [1, 0, 0, 0, 0]

第 1 个 1（j 从 4→1）：
  j=1: dp[1] += dp[0]  → dp[1] = 1
dp = [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, 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
dp = [1, 3, 3, 1, 0]

第 4 个 1：
  j=4: dp[4] += dp[3] = 1
  j=3: dp[3] += dp[2] = 1 + 3 = 4
  j=2: dp[2] += dp[1] = 3 + 3 = 6
  j=1: dp[1] += dp[0] = 4
dp = [1, 4, 6, 4, 1]

第 5 个 1：
  j=4: dp[4] += dp[3] = 1 + 4 = 5 ← 目标
  j=3: dp[3] += dp[2] = 4 + 6 = 10
  j=2: dp[2] += dp[1] = 6 + 4 = 10
  j=1: dp[1] += dp[0] = 5
最终 dp[4] = 5 ✓

复杂度

• 时间复杂度：O(n·P)，两层循环。
• 空间复杂度：O(P)，一维滚动数组。

三种解法对比

解法	时间	空间	特点
纯 DFS（暴力 ±）	O(2ⁿ)	O(n) 栈	代码最直观，n 大时会超时
记忆化 DFS（子集和）	O(n·P)	O(n·P) + 栈	递归好写，带缓存不超时
动态规划（0-1 背包）	O(n·P)	O(P)	空间最优，写法经典

• 推荐写 DP（0-1 背包）或者记忆化 DFS（子集和）。纯暴力只适合小数据或对拍用。

易错点

1. (S + target) 奇偶判断不要漏：奇数时 P 不是整数，直接返回 0，否则后面会出现"和为半整数"，结果必错。
2. (S + target) 负数也要判：虽然 S 非负，但 target 可以是很大的负数，导致 S + target < 0，P 为负，不可能凑出。
3. 记忆 DFS 中 0 方案和"未访问"要区分：方案数可能是 0，所以初始标记用 -1 或其他特殊值，不能用 0。
4. 记忆 DFS 中变量名要对应：原版本把 index/target 写成了 x/sum 这种未定义变量，会直接报错。
5. 0-1 背包一定要倒序：如果正序遍历 j，同一个 num 会被加多次（变成"可选多遍"的完全背包）。
6. nums 里有 0 时也要处理：0 选 + 或 - 表达式一样，但题目算两种不同方案吗？根据题意，"在 0 前面加 +"和"在 0 前面加 -"是两种不同表达式。这三种写法都天然处理好了：0 选进 P 或不选进 P，P = (S+target)/2 不变，但方案数会分开算。

原始版本的 bug 清单

最开始贴的那个"转换后 DFS"版本有几处笔误，这里集中列一下，防止以后抄错：

• nums[x] → x 未定义，应为 nums[index]
• mem[x][sum] → x 和 sum 都未定义，应为 mem[index][target] 或改语义为 mem[index][sum]
• for (let i = 0; i < n; i++) target += nums[i] → n 未定义；且应该是 S += nums[i]，target 不能改
• mem 直接开 1010×1010 不一定够用，按 (n+1) × (P+1) 开更保险
• 而且它的赋值循环结束后，if (target < 0 || target % 2 !== 0) 里判断的那个 target 已经不是题目传入的 target 了，完全乱掉

修正后的代码就是解法二的版本。