494. 目标和 Medium
给你一个非负整数数组 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
解题思路
输入： 一个非负整数数组 nums，一个整数 target
输出： 每个数字前面可以加上 + 或 -，返回通过运算得到 target 的不同表达式数量
本题属于0-1 背包 + 计数型DP问题。
本题有多种解法分别是：
- 记忆化递归（DFS + 缓存）
- 二维 DP 表解法
- 一维 DP（滚动数组优化）
核心转化（0-1 背包 + 计数型 DP）
我们假设：
- 所有数字之和为
s - 所有被加正号的数字之和为
p
那么所有加负号的数字之和就是 s - p 而题目要求的总结果是 p - (s - p) = target
化简可得：
text
2p - s = target => p = (s + target) / 2也就是说，问题转化为：
从数组中挑选一些数字，使得它们的和为
(s + target) // 2，问有多少种选法？
这正是一个典型的 0-1 背包问题（每个数只能选一次），而我们关心的是有多少种选法，所以是 计数型 DP。
条件限制判断：
(s + target)必须是偶数（否则无法整除）p = (s + target) / 2必须是非负整数（否则无解）
解法一：记忆化搜索（递归 + 缓存）
思路：
定义：
dfs(i, c)表示从前i个数中，选出若干个使和为c的方案数转移方程：
- 不选当前数：
dfs(i - 1, c) - 选当前数：
dfs(i - 1, c - nums[i])
- 不选当前数：
终止条件：当
i < 0时，若c == 0表示找到一种方案
解法二：二维 DP 表格法（传统 0-1 背包）
思路：
定义：
dp[i][j]表示从前i个数中，和为j的方案数初始化：
dp[0][0] = 1（不选任何数，和为 0）状态转移：
- 不选当前数：
dp[i][j] = dp[i - 1][j] - 选当前数：
dp[i][j] += dp[i - 1][j - nums[i - 1]]
- 不选当前数：
解法三：一维 DP（空间优化版）
思路：
定义：
dp[c]表示和为c的方案数初始化：
dp[0] = 1遍历每个数
x，从target到x倒序更新：jsdp[c] += dp[c - x]倒序遍历是 0-1 背包的标准写法，避免一个数被重复使用
代码实现
解法一：记忆化搜索（递归 + 缓存）
python
from functools import cache
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total_sum = sum(nums)
# 新的目标和必须是非负且为偶数，才能被拆为两个整数集合
new_target = target + total_sum
if new_target < 0 or new_target % 2 == 1:
return 0
# 转化为：从数组中选一些数，使得它们的和为 new_target // 2
new_target //= 2
n = len(nums)
# 记忆化递归：dfs(i, c) 表示从 nums[0...i] 中选数，使和为 c 的方案数
@cache
def dfs(i: int, c: int) -> int:
# 如果已经没有数可选
if i < 0:
return 1 if c == 0 else 0
# 不选当前数
res = dfs(i - 1, c)
# 如果当前数 ≤ 剩余容量，可以选择它
if c >= nums[i]:
res += dfs(i - 1, c - nums[i])
return res
return dfs(n - 1, new_target)javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
const sum = nums.reduce((acc, curr) => acc + curr, 0);
let new_target = target + sum;
if (new_target < 0 || new_target % 2 == 1) {
return 0
}
new_target /= 2
const cache = {};
function dfs(i, c) {
if (i < 0) return c == 0 ? 1 : 0;
if (cache[`${i} + ${c}`] != null) return cache[`${i} + ${c}`];
let res = dfs(i - 1, c);
if (c >= nums[i]) {
res += dfs(i - 1, c - nums[i]);
}
cache[`${i} + ${c}`] = res;
return res;
}
return dfs(nums.length - 1, new_target);
};解法二：二维 DP 表格法（传统 0-1 背包）
python
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
target += total # 转换成正数子集和 P = (target + sum) / 2
# 如果 target 为负数或不能被 2 整除，说明无法分割成两个子集
if target < 0 or target % 2 == 1:
return 0
target //= 2 # 转化为子集和问题：从 nums 中选出若干数，使得它们的和为 target
n = len(nums)
# f[i][j] 表示前 i 个数中，和为 j 的组合数
f = [[0] * (target + 1) for _ in range(n + 1)]
f[0][0] = 1 # 初始化：不选任何数时，和为 0 的方案数是 1
# 遍历每个数（物品）
for i, x in enumerate(nums):
# 遍历背包容量（目标和）
for j in range(target + 1):
if j < x:
# 当前数 x 放不下，只能继承上一行的方案数
f[i + 1][j] = f[i][j]
else:
# 两种情况：
# 1. 不选当前数 x：f[i][j]
# 2. 选当前数 x：f[i][j - x]
f[i + 1][j] = f[i][j] + f[i][j - x]
# 返回从前 n 个数中，和为 target 的方案数
return f[n][target]javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
// 自底向上解法
const sum = nums.reduce((acc, curr) => acc + curr, 0);
let new_target = target + sum;
if (new_target < 0 || new_target % 2 == 1) {
return 0
}
new_target /= 2
const rows = nums.length + 1;
const cols = new_target + 1;
const f = Array.from({length: rows}, () => Array(cols).fill(0));
f[0][0] = 1;
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < new_target + 1; j++) {
if (j < nums[i]) {
f[i + 1][j] = f[i][j];
} else {
f[i + 1][j] = f[i][j] + f[i][j - nums[i]];
}
}
}
return f[nums.length][new_target];解法三：一维 DP（空间优化版）
python
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 计算数组总和
total = sum(nums)
# 转换问题：令 P - N = target, P + N = total
# 得到 P = (target + total) / 2
target += total # 注意：这里直接把 target 变成 target + total
# 边界判断：不能为负数，也不能是奇数（必须能整除）
if target < 0 or target % 2 == 1:
return 0
# 目标子集和
target //= 2
# 初始化 dp 数组：f[c] 表示和为 c 的方案数
f = [0] * (target + 1)
f[0] = 1 # 和为 0 的方案只有 1 种：不选任何元素
# 遍历每个数
for x in nums:
# 背包从右向左遍历，防止重复使用同一个元素（0-1背包）
for c in range(target, x - 1, -1):
# 状态转移：不选 x + 选 x 的组合
f[c] = f[c] + f[c - x]
# 返回最终能凑出 target 的方案数
return f[target]javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
// 滚动数组优化
const sum = nums.reduce((acc, curr) => acc + curr, 0);
let new_target = target + sum;
if (new_target < 0 || new_target % 2 == 1) {
return 0
}
new_target /= 2
const f = Array(new_target + 1).fill(0);
f[0] = 1;
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
for (let j = new_target; j > x - 1; j--) {
f[j] = f[j] + f[j - nums[i]];
}
}
return f[new_target];复杂度分析
时间复杂度：O(n)
空间复杂度：
- 记忆化搜索（递归 + 缓存）：O(n)
- 二维 DP 表格法（传统 0-1 背包：O(n)
- 一维 DP（空间优化版：O(1)