494. 目标和

494. 目标和

题目描述

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

现在你有两种选择，可以在数组中的每个整数前添加：

  • '+'
  • '-'

然后把所有整数连接起来，构造一个表达式。

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

示例 1

text
输入：nums = [1,1,1,1,1], target = 3
输出：5

示例 2

text
输入：nums = [1], target = 1
输出：1

约束

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

核心思路

这题表面上看是在枚举：

  • 每个数前面加 +
  • 或者加 -

但真正问的是：

  • 一共有多少种方式能凑出 target

所以它本质上是一个：

  • 计数型搜索 / 动态规划 问题

这题至少有两种常见做法：

  • 解法一：DFS / 回溯枚举加减（推荐先理解）
  • 解法二：转化成 0/1 背包计数（推荐掌握）

先理解：为什么能转成背包？

假设我们把数组分成两部分：

  • 一部分前面加 +，它们的和记作 P
  • 一部分前面加 -，它们的和记作 N

那么题目要求：

text
P - N = target

同时所有数总和是：

text
P + N = sum(nums)

两式相加得到：

text
2P = target + sum(nums)

所以：

text
P = (target + sum(nums)) / 2

这就变成了：

  • 从 nums 里选一些数
  • 让它们的和恰好等于 P
  • 问有多少种选法

这就是典型的 0/1 背包计数问题。

但要注意两个前提：

  1. target + sum(nums) 必须是偶数
  2. |target| 不能大于 sum(nums)

否则答案直接是 0。

解法一：DFS / 回溯枚举加减

这是最直观、最适合第一次理解的做法。

思路拆解

对于每个数字 nums[i]，我们都有两种选择：

  • 加上它
  • 减去它

所以可以递归枚举：

text
第 i 个数选 + 还是选 -

递归到最后一个数之后：

  • 如果当前和等于 target，说明找到一种方案
  • 否则不是答案

一步一步写出算法

第一步：定义递归函数

ts
const dfs = (index: number, sum: number): number => {
    ...
}

含义：

  • 当前处理到下标 index
  • 当前表达式和为 sum
  • 返回从这里继续往后能凑出多少种方案

第二步：递归终止条件

如果所有数都处理完了：

ts
if (index === nums.length) {
    return sum === target ? 1 : 0
}

第三步：枚举当前数的两种选择

ts
return dfs(index + 1, sum + nums[index]) + dfs(index + 1, sum - nums[index])

代码实现（TypeScript）

ts
function findTargetSumWays(nums: number[], target: number): number {
    const dfs = (index: number, sum: number): number => {
        if (index === nums.length) {
            return sum === target ? 1 : 0
        }

        return dfs(index + 1, sum + nums[index]) + dfs(index + 1, sum - nums[index])
    }

    return dfs(0, 0)
}

复杂度分析

  • 时间复杂度：O(2^n)
  • 空间复杂度：O(n)

因为每个数都有两种选择。

这一解法的优缺点

优点：

  • 最直观
  • 很容易理解题目本质

缺点：

  • 指数级复杂度
  • 数据稍大就慢

解法二：转化成 0/1 背包计数

这是这题最经典、最推荐掌握的做法。

思路拆解

前面已经推导出：

text
P = (target + sum(nums)) / 2

于是问题转化为：

  • 从数组中选若干个数
  • 恰好装满容量为 P 的背包
  • 问有多少种选法

这是标准的 0/1 背包计数。

我们定义：

ts
dp[j]

表示：

  • 凑出和为 j 的方案数

初始时：

ts
dp[0] = 1

表示：

  • 什么都不选，凑出和 0 有 1 种方式

然后依次遍历每个数，用倒序更新背包。

一步一步写出算法

第一步：先算总和

ts
const sum = nums.reduce((total, num) => total + num, 0)

第二步：先判断无解情况

如果：

ts
Math.abs(target) > sum

说明目标太大，不可能凑出来。

或者：

ts
(sum + target) % 2 !== 0

说明 P 不是整数，也不可能。

直接返回 0。

第三步：计算背包容量

ts
const positive = (sum + target) / 2

第四步：定义 DP 数组

ts
const dp = new Array(positive + 1).fill(0)
dp[0] = 1

第五步：遍历每个数字做 0/1 背包计数

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

为什么要倒序？

因为：

  • 每个数只能用一次
  • 这是 0/1 背包的标准写法

第六步：返回答案

ts
return dp[positive]

代码实现（TypeScript）

ts
function findTargetSumWays(nums: number[], target: number): number {
    const sum = nums.reduce((total, num) => total + num, 0)

    if (Math.abs(target) > sum || (sum + target) % 2 !== 0) {
        return 0
    }

    const positive = (sum + target) / 2
    const dp = new Array(positive + 1).fill(0)
    dp[0] = 1

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

    return dp[positive]
}

4 8  6 9 2 1 =30 10  
=>dp[0]=1 dp[4]=1
=>dp[8]=1 dp[0]=1 dp[4]=1
=>dp[10]=1 dp[8]=1 dp[6]=1  dp[4]=1 dp[0]=1 
=>dp[10]=1 dp[9]=1 dp[8]=1 dp[6]=1  dp[4]=1 dp[0]=1 
=>dp[10]=2 dp[9]=1 dp[8]=2 dp[6]=2  dp[4]=1 dp[2]=1
=>dp[10]=3

复杂度分析

  • 时间复杂度：O(n * positive)
  • 空间复杂度：O(positive)

由于题目里总和不大，这个做法非常适合。

这一解法的优缺点

优点：

  • 复杂度优秀
  • 是这题标准解法
  • 非常适合面试

缺点：

  • 难点在于数学转化
  • 第一次看不太容易想到

两种解法对比

解法时间复杂度空间复杂度特点
DFS / 回溯O(2^n)O(n)最直观，适合入门
0/1 背包计数O(n * positive)O(positive)标准高效解法

如果你是第一次做这题，建议先理解 DFS，再重点掌握背包转化。

手动模拟一遍背包解法

以：

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

为例。

总和：

text
sum = 5

所以：

text
P = (5 + 3) / 2 = 4

问题变成：

  • 从五个 1 里选一些数
  • 让它们和为 4
  • 一共有多少种选法？

显然就是：

  • 选 5 个 1 中的任意 4 个
  • 方案数是 5

所以答案是：

text
5

面试时最容易错的点

1. 这题不是普通求和，是“方案数”

所以 DP 里存的不是布尔值，也不是最大值，而是：

  • 方案数

2. 背包转化前要先判无解

这两句很关键：

ts
Math.abs(target) > sum
(sum + target) % 2 !== 0

3. 0/1 背包一定要倒序

ts
for (let j = positive; j >= num; j--)

否则就会变成完全背包，逻辑错误。

4. 0 这个数字也要正常处理

如果数组里有 0，它会让方案数翻倍。

而上面的 DP 写法本身就能正确处理这一点。

一句话总结

这题的本质是：

给每个数加正负号，等价于把数组分成正集合和负集合，再转成 0/1 背包计数。

  • 想先理解题意：用 DFS 枚举加减
  • 想写标准高效解：用 0/1 背包计数

推荐你最后记住的标准写法

如果你准备刷题，建议优先记下面这个背包版本：

ts
function findTargetSumWays(nums: number[], target: number): number {
    const sum = nums.reduce((total, num) => total + num, 0)

    if (Math.abs(target) > sum || (sum + target) % 2 !== 0) {
        return 0
    }

    const positive = (sum + target) / 2
    const dp = new Array(positive + 1).fill(0)
    dp[0] = 1

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

    return dp[positive]
}

因为这个版本：

  • 是这题公认的标准解法
  • 复杂度优秀
  • 能顺便练到“表达式题转背包”的经典思路