Target Sum Solution

Problem

You are given an array of non-negative integers and a target value. Assign either a + or a - sign before each number, then evaluate the resulting expression. Return the total number of distinct sign assignments that produce the target sum.

Input: nums = [1, 1, 1, 1, 1], target = 3
Output: 5
Explanation: There are 5 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 — each sums to 3.

A counter-example: nums = [1, 2], target = 10 → output 0, because the max reachable sum is ±3, never 10.

Intuition

At every position you make a binary choice — add or subtract — so brute force blows up exponentially. The key insight is that the problem can be reframed as a subset-sum count: if you call the numbers assigned + the "positive subset" P and the rest the "negative subset" N, then sum(P) - sum(N) = target and sum(P) + sum(N) = total, which gives sum(P) = (total + target) / 2. Counting subsets of nums that add up to that fixed value is a classic 0/1 knapsack that runs in O(n · S) time and O(S) space.

Approach 1 — Recursion with Memoization

At each index, recurse with both the + and - choice, caching on (index, current_sum) to avoid recomputing the same subproblem.

Define dfs(index, current_sum) returning the number of ways from index onward to reach target.
Base case: if index == len(nums), return 1 if current_sum == target, else 0.
Check the memo table before computing; return early on a hit.
Recurse into both current_sum + nums[index] (assign +) and current_sum - nums[index] (assign -), sum the results.
Store and return the combined count.

1def findTargetSumWays(nums: list[int], target: int) -> int:
2    memo = {}
3
4    def dfs(index: int, current_sum: int) -> int:
5        if index == len(nums):
6            return 1 if current_sum == target else 0
7        if (index, current_sum) in memo:
8            return memo[(index, current_sum)]
9        add_ways = dfs(index + 1, current_sum + nums[index])
10        subtract_ways = dfs(index + 1, current_sum - nums[index])
11        memo[(index, current_sum)] = add_ways + subtract_ways
12        return memo[(index, current_sum)]
13
14    return dfs(0, 0)

Time: O(n · S) — each (index, sum) pair is computed once; total sums range over [−total, +total], giving at most 2·n·total unique states.

Space: O(n · S) — memo table plus recursion stack depth n.

Approach 2 — Bottom-up DP (Subset Sum Reformulation)

Reformulate: let subset_sum = (total + target) / 2, then count subsets of nums that add to exactly subset_sum. Use a 1-D DP array where dp[j] holds the number of subsets summing to j, iterating each number in reverse to enforce the 0/1 constraint.

Compute total = sum(nums). Return 0 if abs(target) > total or (total + target) is odd — no valid assignment exists.
Set subset_sum = (total + target) // 2.
Initialize dp[0] = 1 (one way to reach sum 0: pick nothing), all others 0.
For each num, iterate j from subset_sum down to num, adding dp[j - num] to dp[j].
Return dp[subset_sum].

1def findTargetSumWays(nums: list[int], target: int) -> int:
2    total = sum(nums)
3    # No valid assignment if target is unreachable or subset_sum is fractional
4    if abs(target) > total or (total + target) % 2 != 0:
5        return 0
6
7    subset_sum = (total + target) // 2
8    dp = [0] * (subset_sum + 1)
9    dp[0] = 1  # empty subset always sums to 0
10
11    for num in nums:
12        # Reverse iteration prevents using num more than once per assignment
13        for j in range(subset_sum, num - 1, -1):
14            dp[j] += dp[j - num]
15
16    return dp[subset_sum]

Time: O(n · S) — same asymptotic as memoization, where S = (total + target) / 2 ≤ total.

Space: O(S) — single 1-D DP array; no recursion overhead.

Complexity Summary

Approach	Time	Space	When to use
Recursion with Memoization	O(n · S)	O(n · S)	More intuitive starting point; works even when subset_sum is not well-defined
Bottom-up DP (Subset Sum)	O(n · S)	O(S)	Preferred in production — no recursion overhead and minimal memory

Common Mistakes

Skipping the early-exit checks in Approach 2 — if abs(target) > total, subset_sum would be negative; if (total + target) is odd, subset_sum is fractional. Either omission causes a wrong answer or an array index error.
Iterating the inner DP loop forward (ascending j) instead of backward — ascending order lets each num contribute to later indices in the same pass, effectively counting it multiple times and turning the problem into unbounded knapsack. The count explodes incorrectly.
Keying the memo only on index — the return value depends on both index and current_sum; caching on index alone causes the first-reached sum at that index to be returned for all subsequent sums, producing wildly wrong counts.
Treating a negative target as impossible — since you freely assign signs, a negative target is valid as long as abs(target) ≤ total. The guard condition is abs(target) > total, not target < 0.
Forgetting that total + target can overflow for large inputs — in Java and C++, if total and target are both near INT_MAX, the addition overflows. Use long or check bounds before the addition.

Target Sum — Solution