DP — Target Sum
↗ LeetCode: Target Sum · Medium · pattern chapter →
Asked atMetaAmazonGoogle
Assign + or − to each nums[i]; count ways to reach target.
Example 1 — nums=[1,1,1,1,1], target=3 → 5Example 2 — nums=[1], target=1 → 1
Constraints — 1 ≤ n ≤ 20. Brute enumerates ±assignments — O(2ⁿ) = 10⁶ ops at n=20 (fine), but 10³⁰ ops at n=100. Knapsack DP is O(n·sum) ≤ 20·10⁴ = 2·10⁵ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Backtracking
O(2ⁿ). Baseline.
Approach 2 — Reduce to subset-sum count (canonical)
Insight. P - N = target, P + N = total → P = (total + target) / 2. Count subsets summing to P.
java
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[] dp = new int[P + 1];
dp[0] = 1;
for (int x : nums)
for (int j = P; j >= x; j--)
dp[j] += dp[j - x];
return dp[P];
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n · P); Space O(P).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Backtracking | O(2ⁿ) | O(n) | baseline |
| Reduce + subset-sum | O(n · P) | O(P) | canonical |
When to use which
- ± assignment counting → reduce to subset-sum.
- Return the assignment → track parent choices.
AI Study CompanionBeta
Related problems
Was this page helpful?