LeetCode 494: Target Sum (Sign Assignment → Subset Sum DP)
LeetCode 494DPKnapsackToday we solve LeetCode 494 - Target Sum.
Source: https://leetcode.com/problems/target-sum/
English
Problem Summary
Given an integer array nums and an integer target, assign either + or - before every number, then evaluate the expression. Return how many different sign assignments produce exactly target.
Key Insight
Let P be the sum of numbers assigned +, and N be the sum of numbers assigned -. Then:
P - N = target, P + N = total ⇒ 2P = total + target ⇒ P = (total + target) / 2.
So the problem becomes: count subsets whose sum is P. This is classic 0/1 knapsack counting DP.
Algorithm
1) Compute total = sum(nums).
2) If |target| > total or (total + target) is odd, return 0.
3) Set goal = (total + target) / 2.
4) Use 1D DP where dp[s] = number of ways to form sum s.
5) Initialize dp[0] = 1. For each num, iterate s from goal down to num:
dp[s] += dp[s - num].
6) Return dp[goal].
Complexity
Time: O(n * goal).
Space: O(goal).
Common Pitfalls
- Forgetting parity check for total + target.
- Iterating DP forward (would reuse one element multiple times). Must iterate backward.
- Mishandling zero values: zeros naturally double counts through the same transition, which is correct.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int x : nums) total += x;
if (Math.abs(target) > total) return 0;
int sum = total + target;
if ((sum & 1) != 0) return 0;
int goal = sum / 2;
int[] dp = new int[goal + 1];
dp[0] = 1;
for (int num : nums) {
for (int s = goal; s >= num; s--) {
dp[s] += dp[s - num];
}
}
return dp[goal];
}
}func findTargetSumWays(nums []int, target int) int {
total := 0
for _, x := range nums {
total += x
}
if target > total || target < -total {
return 0
}
sum := total + target
if sum%2 != 0 {
return 0
}
goal := sum / 2
dp := make([]int, goal+1)
dp[0] = 1
for _, num := range nums {
for s := goal; s >= num; s-- {
dp[s] += dp[s-num]
}
}
return dp[goal]
}class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int total = 0;
for (int x : nums) total += x;
if (abs(target) > total) return 0;
int sum = total + target;
if (sum % 2 != 0) return 0;
int goal = sum / 2;
vector<int> dp(goal + 1, 0);
dp[0] = 1;
for (int num : nums) {
for (int s = goal; s >= num; --s) {
dp[s] += dp[s - num];
}
}
return dp[goal];
}
};class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
total = sum(nums)
if abs(target) > total:
return 0
s = total + target
if s % 2:
return 0
goal = s // 2
dp = [0] * (goal + 1)
dp[0] = 1
for num in nums:
for cur in range(goal, num - 1, -1):
dp[cur] += dp[cur - num]
return dp[goal]/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
let total = 0;
for (const x of nums) total += x;
if (Math.abs(target) > total) return 0;
const sum = total + target;
if (sum % 2 !== 0) return 0;
const goal = Math.floor(sum / 2);
const dp = new Array(goal + 1).fill(0);
dp[0] = 1;
for (const num of nums) {
for (let s = goal; s >= num; s--) {
dp[s] += dp[s - num];
}
}
return dp[goal];
};中文
题目概述
给定整数数组 nums 和整数 target，你要给每个数字前面加上 + 或 -，最终表达式结果等于 target。求满足条件的不同符号分配方案数。
核心思路
设加号集合和为 P，减号集合和为 N，则：
P - N = target，P + N = total，联立得 P = (total + target) / 2。
问题就转化为：从数组中选若干数，使其和恰好为 P，求方案数，即 0/1 背包计数 DP。
算法步骤
1）计算 total = sum(nums)。
2）若 |target| > total 或 total + target 为奇数，直接返回 0。
3）令 goal = (total + target) / 2。
4）定义 dp[s] 表示凑出和 s 的方案数。
5）初始化 dp[0] = 1。遍历每个 num，s 从 goal 逆序到 num：
dp[s] += dp[s - num]。
6）答案是 dp[goal]。
复杂度分析
时间复杂度：O(n * goal)。
空间复杂度：O(goal)。
常见陷阱
- 漏掉 total + target 奇偶性判断。
- 背包循环写成正序会导致同一元素被重复使用。
- 对 0 的处理不用特判，DP 转移会自然把方案数翻倍，这是正确行为。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int x : nums) total += x;
if (Math.abs(target) > total) return 0;
int sum = total + target;
if ((sum & 1) != 0) return 0;
int goal = sum / 2;
int[] dp = new int[goal + 1];
dp[0] = 1;
for (int num : nums) {
for (int s = goal; s >= num; s--) {
dp[s] += dp[s - num];
}
}
return dp[goal];
}
}func findTargetSumWays(nums []int, target int) int {
total := 0
for _, x := range nums {
total += x
}
if target > total || target < -total {
return 0
}
sum := total + target
if sum%2 != 0 {
return 0
}
goal := sum / 2
dp := make([]int, goal+1)
dp[0] = 1
for _, num := range nums {
for s := goal; s >= num; s-- {
dp[s] += dp[s-num]
}
}
return dp[goal]
}class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int total = 0;
for (int x : nums) total += x;
if (abs(target) > total) return 0;
int sum = total + target;
if (sum % 2 != 0) return 0;
int goal = sum / 2;
vector<int> dp(goal + 1, 0);
dp[0] = 1;
for (int num : nums) {
for (int s = goal; s >= num; --s) {
dp[s] += dp[s - num];
}
}
return dp[goal];
}
};class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
total = sum(nums)
if abs(target) > total:
return 0
s = total + target
if s % 2:
return 0
goal = s // 2
dp = [0] * (goal + 1)
dp[0] = 1
for num in nums:
for cur in range(goal, num - 1, -1):
dp[cur] += dp[cur - num]
return dp[goal]/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
let total = 0;
for (const x of nums) total += x;
if (Math.abs(target) > total) return 0;
const sum = total + target;
if (sum % 2 !== 0) return 0;
const goal = Math.floor(sum / 2);
const dp = new Array(goal + 1).fill(0);
dp[0] = 1;
for (const num of nums) {
for (let s = goal; s >= num; s--) {
dp[s] += dp[s - num];
}
}
return dp[goal];
};
Comments