494. 目标和
题目描述
输入非负整数数组 nums 和整数 target。
给每个元素前面添上 + 或 - 号，再按原顺序连起来，得到一个算式。例如 nums = [2,1] 可以写成 +2-1。
返回计算结果等于 target 的算式有多少种。符号选择不同就算不同的算式。
示例 1
输入：nums = [1,1,1,1,1], target = 3 输出：5
解释：五个 1 中恰好一个取负号时和为 3，负号可放在任一位置，共 5 种。
示例 2
输入：nums = [1], target = 1 输出：1
解释：只有 +1 等于 1。
数据范围
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
解题思路：动态规划（转化为 0-1 背包）
设取负号的数之和为 neg，则 (total - neg) - neg = target，得 neg = (total - target) / 2。问题变成：从 nums 中选若干个数使和恰好为 neg，有多少种选法。这是 0-1 背包计数：dp[j] 表示和为 j 的选法数，每个数 x 只能用一次，所以 j 从大到小更新 dp[j] += dp[j - x]。若 total + target 是奇数或 |target| > total，直接无解。
为什么正确
处理完前 i 个数后，dp[j] 恰好等于在前 i 个数中选若干个、和为 j 的方案数。
复杂度分析
时间 O(n * neg)，空间 O(neg)。
易错点
j 必须倒序遍历，否则同一个 x 会被重复使用；另外 nums 中的 0 会让方案数翻倍，倒序到 j = x 也能正确处理。别忘了先判断 total + target 的奇偶和 |target| > total。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
if abs(target) > total or (total + target) % 2:
return 0
neg = (total - target) // 2
dp = [1] + [0] * neg
for x in nums:
for j in range(neg, x - 1, -1):
dp[j] += dp[j - x]
return dp[neg]class Solution {
public int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int v : nums) total += v;
if (Math.abs(target) > total || (total + target) % 2 != 0) {
return 0;
}
int neg = (total - target) / 2;
int[] dp = new int[neg + 1];
dp[0] = 1;
for (int x : nums) {
for (int j = neg; j >= x; j--) {
dp[j] += dp[j - x];
}
}
return dp[neg];
}
}class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int total = accumulate(nums.begin(), nums.end(), 0);
if (abs(target) > total || (total + target) % 2) {
return 0;
}
int neg = (total - target) / 2;
vector<int> dp(neg + 1, 0);
dp[0] = 1;
for (int x : nums) {
for (int j = neg; j >= x; j--) {
dp[j] += dp[j - x];
}
}
return dp[neg];
}
};func findTargetSumWays(nums []int, target int) int {
total := 0
for _, v := range nums {
total += v
}
if target > total || -target > total || (total+target)%2 != 0 {
return 0
}
neg := (total - target) / 2
dp := make([]int, neg+1)
dp[0] = 1
for _, x := range nums {
for j := neg; j >= x; j-- {
dp[j] += dp[j-x]
}
}
return dp[neg]
}var findTargetSumWays = function(nums, target) {
const total = nums.reduce((a, b) => a + b, 0);
if (Math.abs(target) > total || (total + target) % 2 !== 0) {
return 0;
}
const neg = (total - target) / 2;
const dp = new Array(neg + 1).fill(0);
dp[0] = 1;
for (const x of nums) {
for (let j = neg; j >= x; j--) {
dp[j] += dp[j - x];
}
}
return dp[neg];
};function findTargetSumWays(nums: number[], target: number): number {
const total = nums.reduce((a, b) => a + b, 0);
if (Math.abs(target) > total || (total + target) % 2 !== 0) {
return 0;
}
const neg = (total - target) / 2;
const dp: number[] = new Array(neg + 1).fill(0);
dp[0] = 1;
for (const x of nums) {
for (let j = neg; j >= x; j--) {
dp[j] += dp[j - x];
}
}
return dp[neg];
}其他解法
回溯直接枚举所有符号组合；动态规划把问题转化为“选若干数和为 (sum − target)/2”的背包计数，复杂度与数值大小有关而不是指数级。
解法 2：回溯 时间 O(2ⁿ)，空间 O(n)
按顺序给每个数尝试 + 和 − 两种符号，递归到末尾时，若累计和等于 target 就计数 1。两条分支的结果相加就是答案。
不需要做任何数学转化，最容易想到。时间是 2ⁿ，只适用于 n ≤ 20 这样的小规模。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
# 回溯：每个数依次尝试取 + 和取 -
def dfs(i, s):
if i == n:
return 1 if s == target else 0
return dfs(i + 1, s + nums[i]) + dfs(i + 1, s - nums[i])
return dfs(0, 0)class Solution {
private int dfs(int[] nums, int target, int i, int s) {
if (i == nums.length) return s == target ? 1 : 0;
return dfs(nums, target, i + 1, s + nums[i]) + dfs(nums, target, i + 1, s - nums[i]);
}
public int findTargetSumWays(int[] nums, int target) {
return dfs(nums, target, 0, 0);
}
}class Solution {
public:
int dfs(vector<int>& nums, int target, int i, int s) {
if (i == (int)nums.size()) return s == target ? 1 : 0;
return dfs(nums, target, i + 1, s + nums[i]) + dfs(nums, target, i + 1, s - nums[i]);
}
int findTargetSumWays(vector<int>& nums, int target) {
return dfs(nums, target, 0, 0);
}
};func findTargetSumWays(nums []int, target int) int {
var dfs func(i, s int) int
dfs = func(i, s int) int {
if i == len(nums) {
if s == target {
return 1
}
return 0
}
return dfs(i+1, s+nums[i]) + dfs(i+1, s-nums[i])
}
return dfs(0, 0)
}var findTargetSumWays = function(nums, target) {
const dfs = (i, s) => {
if (i === nums.length) return s === target ? 1 : 0;
return dfs(i + 1, s + nums[i]) + dfs(i + 1, s - nums[i]);
};
return dfs(0, 0);
};function findTargetSumWays(nums: number[], target: number): number {
const dfs = (i: number, s: number): number => {
if (i === nums.length) return s === target ? 1 : 0;
return dfs(i + 1, s + nums[i]) + dfs(i + 1, s - nums[i]);
};
return dfs(0, 0);
}