#494
Target Sum
Medium 0/1 knapsack (count subsets)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Put + or − in front of every number. Count the sign choices that make the expression equal target.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: ways to put + or − before each number to reach target.
Why this works: the plus group P must equal (total + target) / 2, so count subsets with that sum.
Example: [1, 1, 1, 1, 1], target 3 → P = 4
ways to choose 4 ones out of 5 → 5✦Hints open one at a time
Let P = numbers with +, N = numbers with −. P − N = target and P + N = total.
So P = (total + target) / 2. Count subsets with that sum.
↗Approach
If (total + target) is odd or |target| > total, return 0. Otherwise count subsets summing to P with the 0/1 knapsack counting DP (downward loop).
</>Solution (Java)
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int x : nums) total += x;
if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;
int p = (total + target) / 2;
int[] ways = new int[p + 1];
ways[0] = 1;
for (int x : nums) {
for (int s = p; s >= x; s--) ways[s] += ways[s - x]; // each number once
}
return ways[p];
}
}!Common mistake
Missing zeros: each 0 doubles the count — the DP handles it naturally if dp[0] starts at 1 and you loop down to x (including s = x = 0).
Complexity
- Time: O(n · P).
- Space: O(P).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon