494. 目标和
494. 目标和
题目链接（中等）
题目描述
给你一个非负整数数组 nums 和一个整数 target。
向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数，可以构造一个 表达式。
例如，nums = [2, 1]，可以在 2 之前添加 '+'，在 1 之前添加 '-'，然后串联起来得到表达式 "+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
数据范围：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
示例
示例 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
核心思路
每个元素可以加 + 或 -，共 2^n 种符号方案。要求结果等于 target 的方案数。
两种主流思路：
- 回溯：直接枚举所有符号组合，统计和等于
target的方案数，时间 $O(2^n)$； - 动态规划（转成 0-1 背包）：通过数学推导把问题转成「选数凑和」的方案数问题，时间与
sum有关。
方法一：回溯（暴力枚举）
思路及解法
每个元素有两种选择：加 + 或加 -。递归枚举所有情况，到叶子节点时检查表达式结果是否等于 target。
递归结构：
dfs(i, current_sum)：处理第i个元素时，当前表达式的和为current_sum；- 终止条件：
i == n时，判断current_sum == target，是则计数 +1； - 递归分支：
dfs(i+1, current_sum + nums[i])和dfs(i+1, current_sum - nums[i])。
为什么可以用回溯：题目数据规模小（n <= 20），$2^{20} \approx 10^6$，完全可以接受。
代码
class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
n = len(nums)
count = 0
def dfs(i: int, current_sum: int) -> None:
nonlocal count
if i == n:
if current_sum == target:
count += 1
return
dfs(i + 1, current_sum + nums[i])
dfs(i + 1, current_sum - nums[i])
dfs(0, 0)
return count复杂度分析
- 时间复杂度：$O(2^n)$，共 $2^n$ 种符号组合，每种组合 $O(1)$ 判断。
- 空间复杂度：$O(n)$，递归栈深度为
n。
方法二：动态规划（转成 0-1 背包）
思路及解法
关键推导：
设数组元素和为 sum，所有添加 + 的元素之和为 pos，添加 - 的元素之和为 neg，则：
表达式的结果为：
两式相加、相减可得：
因此，问题转化为：从 nums 中选出若干个数，使其和恰好等于 neg，求方案数。
成立条件（预处理）：
diff = sum - target必须>= 0；diff必须是偶数，否则返回 0；- 令
neg = diff / 2，作为背包容量。
状态定义：dp[i][j] 表示「从 nums[0..i-1] 中选若干个数，和为 j 的方案数」。
转移方程：
对于第 i 个元素（nums[i-1]）：
- 不选：
dp[i-1][j]； - 选（前提
j >= nums[i-1]）：dp[i-1][j - nums[i-1]]。
边界条件：dp[0][0] = 1（不选任何数，和为 0 有一种方案），其余 dp[0][j] = 0。
答案：dp[n][neg]。
代码
class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
total = sum(nums)
diff = total - target
# 预处理：差值必须非负且为偶数
if diff < 0 or diff % 2 != 0:
return 0
neg = diff // 2
n = len(nums)
# dp[i][j]：前 i 个数中和为 j 的方案数
dp = [[0] * (neg + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
num = nums[i - 1]
for j in range(neg + 1):
dp[i][j] = dp[i - 1][j]
if j >= num:
dp[i][j] += dp[i - 1][j - num]
return dp[n][neg]复杂度分析
- 时间复杂度：$O(n \cdot neg)$，共 $n \times (neg + 1)$ 个状态，每个状态 $O(1)$ 转移。
- 空间复杂度：$O(n \cdot neg)$，二维
dp数组。
方法三：动态规划 + 滚动数组（$O(neg)$ 空间）✅ 推荐
思路及解法
dp[i][j] 只依赖 dp[i-1][*]，可以用一维数组压缩空间。
状态定义：dp[j] 表示「当前和为 j 的方案数」。
转移方程：
关键：内层遍历 j 必须从大到小（倒序）！
为什么倒序？
- 0-1 背包中，每个元素只能用一次；
- 正序遍历时，
dp[j - num]可能已在本轮被更新过（即同一个元素用了多次），变成完全背包； - 倒序遍历时，
dp[j - num]是上一轮的值，保证每个元素只用一次。
边界：dp[0] = 1。
答案：dp[neg]。
代码
class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
total = sum(nums)
if total < target or (total - target) % 2 != 0:
return 0
neg = (total - target) // 2
dp = [0] * (neg + 1)
dp[0] = 1
for num in nums:
# 倒序遍历，保证每个数只用一次
for j in range(neg, num - 1, -1):
dp[j] += dp[j - num]
return dp[neg]复杂度分析
- 时间复杂度：$O(n \cdot neg)$。
- 空间复杂度：$O(neg)$，一维
dp数组。
三种方法对比
| 方法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 回溯 | $O(2^n)$ | $O(n)$ | 思路最直观，适合小数据 |
| DP（二维） | $O(n \cdot neg)$ | $O(n \cdot neg)$ | 状态清晰，便于理解 |
| DP（滚动） | $O(n \cdot neg)$ | $O(neg)$ | 空间最优，面试首选 |
推荐：
- 面试开场：先讲回溯，因为它直接对应题目描述；
- 追问优化：再讲DP + 滚动数组，展示数学推导和空间优化能力。
关键细节
1. 数学推导的核心
设添加 + 的和为 pos，添加 - 的和为 neg：
解得 neg = (sum - target) / 2。所以问题转化为「选数凑 neg」的方案数。
2. 为什么用 0-1 背包而不是完全背包
每个元素最多被选一次（要么放进 neg，要么放进 pos），符合 0-1 背包的特征。所以内层遍历倒序。
3. dp[0] = 1 的含义
和为 0 的方案总是存在（一个都不选），这是递推的基石。
4. 元素可以为 0 的处理
本题允许 nums[i] = 0。对于 0：
- 选或不选，和都不变；
- 但两个选择是不同的方案（因为符号不同）；
- DP 转移中
dp[j] += dp[j - 0]，相当于把dp[j]翻倍，正确处理了这种「两种符号都合法」的情况。
5. 边界与非法输入
diff < 0：即使全加-也达不到target（因为target > sum）；diff % 2 != 0：neg不是整数，无解。
这两种情况都要提前返回 0。
6. 与 LC 416（分割等和子集）的区别
| LC 416 | LC 494 | |
|---|---|---|
| 目标 | 能否凑出 target |
凑出 neg 的方案数 |
| DP 值 | 布尔值 | 整数（方案数） |
| 转移 | dp[j] = dp[j] or dp[j-num] |
dp[j] += dp[j-num] |
两者都是 0-1 背包，但一个求「可行性」，一个求「方案数」。
总结
- 问题转化：选数凑
neg = (sum - target) / 2，求方案数； - 预处理：
diff = sum - target必须>= 0且为偶数； - 回溯方法：
- 枚举每个元素的符号；
- 时间 $O(2^n)$，适合小数据；
- DP 方法：
dp[j]表示和为j的方案数；- 转移：
dp[j] += dp[j - num]； - 内层倒序（0-1 背包核心）；
- 边界：
dp[0] = 1； - 时间 $O(n \cdot neg)$、空间 $O(neg)$；
- 通用套路：「正负号分配」→「选数凑和」→ 0-1 背包方案数。
相关题目
- LC 416. 分割等和子集（0-1 背包，求可行性）
- LC 322. 零钱兑换（完全背包，求最少数量）
- LC 518. 零钱兑换 II（完全背包，求方案数）
- LC 279. 完全平方数（完全背包）
- LC 1049. 最后一块石头的重量 II（0-1 背包，最小差）