LeetCode · #494

Target Sum Solution

Assign a + or - to each element so the sum equals target. Return the number of ways.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #494

🏗️

Pattern

DP — subset sum / knapsack

Given array nums and integer target, assign + or - to each element. Return how many different assignments make the sum equal to target.

Example

Input: nums = [1,1,1,1,1], target = 3 Output: 5 // Five ways: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1

Constraints

• 1 ≤ nums.length ≤ 20 • 0 ≤ nums[i] ≤ 1000,  0 ≤ sum(nums) ≤ 1000 • -1000 ≤ target ≤ 1000

Section Two · Approach 1

Recursion — O(2ⁿ)

For each element, try + or -. Recurse on remaining elements with updated running sum. Count leaves where sum equals target.

Why it works

Exhaustively explores all 2ⁿ sign assignments. Every valid combination is counted.

Why we can do better

Problem: 2²⁰ = ~1 million. Manageable for n=20, but the DP approach reduces to O(n·S) where S = sum of all elements. The key insight: let P = sum of elements with +, N = sum with -. Then P - N = target and P + N = totalSum. So P = (target + totalSum) / 2. The problem reduces to: count subsets with sum P — a standard 0/1 knapsack.

Java — Recursive

 class Solution {
public int findTargetSumWays(int[] nums, int target) {
return dfs(nums, target, 0, 0);
    }
private int dfs(int[] nums, int target, int i, int sum) {
if (i == nums.length) return sum == target ? 1 : 0;
return dfs(nums, target, i+1, sum+nums[i])
             + dfs(nums, target, i+1, sum-nums[i]);
    }
}

Python — Recursive

 class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
def dfs(i, s):
if i == len(nums): return 1 if s == target else 0 return dfs(i+1, s+nums[i]) + dfs(i+1, s-nums[i])
return dfs(0, 0)

Metric	Value
Time	O(2ⁿ)
Space	O(n)

Section Three · Approach 2

Subset Sum DP — O(n · S)

Transform: P = (totalSum + target) / 2. Count subsets summing to P using 1D knapsack DP. If (totalSum + target) is odd or negative, return 0.

💡 Mental model: Splitting numbers into + and − groups is like dividing a pile of coins into two boxes. The difference between boxes must equal the target. But difference constraints are tricky — convert to: the "positive box" must weigh exactly (total + target) / 2. Now it's a standard knapsack: how many ways can you fill a box to exact weight P?

Algorithm

Compute totalSum. If (totalSum + target) is odd or |target| > totalSum: return 0.
Let P = (totalSum + target) / 2.
dp[s] = number of subsets summing to s. Init: dp[0] = 1.
For each num: iterate s from P down to num: dp[s] += dp[s - num].
Return dp[P].

🎯 When to recognize this pattern: "+/- assignment to reach target" = subset sum in disguise. The algebraic trick P = (sum + target)/2 converts a ±partition into a standard knapsack. Also applies to LC 416 (Partition Equal Subset Sum) and LC 1049 (Last Stone Weight II).

Why iterate s backwards: Processing s from high to low ensures each element is used at most once (0/1 knapsack). Forward iteration would allow reusing elements (unbounded knapsack).

Section Four · Trace

Visual Walkthrough

Trace for nums=[1,1,1,1,1], target=3. totalSum=5, P=(5+3)/2=4.

Target Sum → Subset Sum DP (P=4)

Section Five · Implementation

Code — Java & Python

Java — Subset Sum DP

 class Solution {
public int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int n : nums) total += n;
if ((total + target) % 2 != 0 || total + target < 0) return 0;
int P = (total + target) / 2;
int[] dp = new int[P + 1];
        dp[0] = 1; // empty subset sums to 0 for (int num : nums)
for (int s = P; s >= num; s--) // 0/1 knapsack: backward
dp[s] += dp[s - num];
return dp[P];
    }
}

Python — Subset Sum DP

 class Solution:
def findTargetSumWays(self, nums: list[int], target: int) -> int:
        total = sum(nums)
if (total + target) % 2 or total + target < 0: return 0
P = (total + target) // 2
dp = [0] * (P + 1)
        dp[0] = 1 for num in nums:
for s in range(P, num - 1, -1):
                dp[s] += dp[s - num]
return dp[P]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursion	O(2ⁿ)	O(n)	Simple but exponential
Memoized DFS	O(n·S)	O(n·S)	Top-down; requires offset for negative sums
Subset Sum DP ← optimal	O(n·P)	O(P)	1D array; elegant math reduction

Why not 2D offset DP? A 2D table indexed by (element, running sum + offset) works but requires O(n·2S) space. The subset-sum reduction halves the problem size and uses a clean 1D array.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Impossible (odd)	`[1], target=2`	(1+2)=3 is odd → return 0.
Target larger than sum	`[1,1], target=5`	\|target\| > totalSum → return 0.
Zeros in array	`[0,0,1], target=1`	Each 0 can be + or −, doubling ways: 4.
All zeros	`[0,0], target=0`	Every assignment works: 2²=4 ways.
Single element	`[5], target=5`	Only +5 works. P=(5+5)/2=5, dp[5]=1.

⚠ Common Mistake: Forgetting that nums can contain zeros. A zero contributes 0 whether it's +0 or -0, but it still doubles the number of ways. The DP handles this correctly because dp[s] += dp[s - 0] = dp[s] += dp[s] = doubles the count.

← Back to DP — 2D problems

LearningTree

LC 494 · Target Sum — Solution & Explanation | DSA Guide