4.24.5 — Target Sum

LeetCode 494 · Medium

The problem

Put a + or a − in front of every number, then add them up. How many assignments produce the target?

nums = [1,1,1,1,1], target = 3   →  5
    -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[i]) <= 1000
• -1000 <= target <= 1000

Plain-English Restatement: You have a list of numbers. For every number, you must choose to either add it or subtract it. Your goal is to find how many different ways you can assign these plus and minus signs so that the final evaluated math expression equals a specific target number.

Brute Force Approach: As mentioned in the pattern, the brute force approach is to try every possible combination of signs. We can write a recursive function that at index i branches into two paths: one adding nums[i] to our running total, and one subtracting it.

• Time Complexity: O(2^n). There are 2 choices for each of the n numbers. For n=20, 2^{20} \approx 1,000,000, which actually passes on LeetCode but is slow. For n=40, it would immediately time out.
• Why it's wasteful: If we have [1, 1, 1, 1...], doing +1 -1 and -1 +1 both result in a running sum of 0 at index 2. The brute force approach calculates the remaining 18 numbers identically for both branches. DP/Memoization merges these identical states.

The pattern

The brute force tries 2^n sign assignments. With n = 20 that is a million, which actually passes — but the intended solution is much better and comes from a short piece of algebra.

Split the numbers into two groups: P gets a plus, N gets a minus. Then:

\text{sum}(P) - \text{sum}(N) = \text{target}

And of course:

\text{sum}(P) + \text{sum}(N) = \text{total}

Add the two equations. The sum(N) terms cancel:

2 \times \text{sum}(P) = \text{target} + \text{total}

\text{sum}(P) = \frac{\text{target} + \text{total}}{2}

So the question becomes: how many subsets sum to (target + total) / 2?

That is a counting subset-sum, and you already have the machinery — 4.23.12 with + instead of or.

The reduction is the problem. Once you have it, the code is eight lines.

The two impossibility checks

The formula only makes sense under two conditions, and both must be checked before running anything.

(target + total) must be even, or sum(P) would not be a whole number. Odd means no assignment works, so return 0.

|target| must not exceed total. You cannot reach a target further from zero than the sum of everything. In code, abs(target) > total → 0.

Both are one line each, and forgetting either produces a negative or fractional array size, which crashes rather than returning 0.

The solution

Python

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)

        if abs(target) > total or (target + total) % 2:
            return 0                          # impossible

        subset_target = (target + total) // 2

        dp = [0] * (subset_target + 1)
        dp[0] = 1                             # one way to make 0: choose nothing

        for n in nums:
            for t in range(subset_target, n - 1, -1):     # DOWNWARDS: each once
                dp[t] += dp[t - n]

        return dp[subset_target]

TypeScript

function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0);

  if (Math.abs(target) > total || (target + total) % 2 !== 0) return 0;

  const subsetTarget = (target + total) / 2;
  const dp = new Array(subsetTarget + 1).fill(0);
  dp[0] = 1;

  for (const n of nums) {
    for (let t = subsetTarget; t >= n; t--) {
      dp[t] += dp[t - n];
    }
  }

  return dp[subsetTarget];
}

The inner loop counts downwards, because each number gets exactly one sign — it is used once. Counting upwards would let a number be used repeatedly, which is the unbounded knapsack and a different problem. That is the direction rule from 4.22 and 4.24.4.

dp[0] = 1 — one way to make zero, by choosing nothing. Every count is built from it.

Zeros in the input work correctly, and they are worth checking. A zero can carry either sign, so it doubles the number of assignments. In this code, processing a 0 runs dp[t] += dp[t - 0], which doubles every entry — exactly right, and it happens with no special case.

Trace

nums = [1,1,1,1,1], target = 3. Total is 5, so subset_target = (3 + 5) / 2 = 4.

You need subsets of four 1s from five, and there are \binom{5}{4} = 5 of them ✓ — matching the five sign assignments in the problem statement.

The direct DP, without the reduction

If the algebra does not arrive, there is a solution that works straight from the problem: track how many ways reach each running sum.

from collections import defaultdict

def findTargetSumWays(self, nums, target):
    ways = {0: 1}
    for n in nums:
        nxt = defaultdict(int)
        for s, count in ways.items():
            nxt[s + n] += count
            nxt[s - n] += count
        ways = nxt
    return ways.get(target, 0)

The number of distinct running sums is bounded by 2 × total + 1, so this is O(n \times \text{total}) — the same complexity, using a dictionary because sums can be negative.

Say this one if the reduction does not come to you. A correct solution of the right complexity beats a stalled attempt at the elegant one.

Complexity

O(n \times \text{total}) time, O(\text{total}) space.

Pseudo-polynomial again, exactly as in 4.23.12 — polynomial in the value of the sum, not in the input size.

Code Walkthrough (Algebraic DP)

1. Calculate Math: We compute subset_target = (target + total) // 2.
2. Setup DP: dp = [0] * (subset_target + 1). dp[t] will hold the number of ways to pick a subset of numbers that sum to exactly t.
3. Base Case: dp[0] = 1. There's exactly 1 way to get a sum of 0: pick none of the numbers.
4. Outer Loop: for n in nums:. We consider each number one by one.
5. Inner Loop (Downwards): for t in range(subset_target, n - 1, -1):. We iterate backwards from the target down to n. We stop at n because we can't possibly use n to make a sum smaller than n.
6. The Transition: dp[t] += dp[t - n]. We update the number of ways to make sum t by adding the number of ways we could make t - n. Because we iterate backwards, dp[t - n] still contains the value from the previous step (before we considered the current n). This guarantees we use n at most once.

Complexity Derivation

• Time Complexity: O(n \times \text{total}). The subset target is bounded by total. We have an outer loop of size n, and an inner loop of size at most total.
• Space Complexity: O(\text{total}). We use a 1D array of size subset_target + 1, which scales linearly with the sum of the array elements.

Edge Cases

• Target is impossible to reach (too large): If abs(target) > total, we catch it early and return 0.
• Target is impossible to reach (parity mismatch): If (target + total) is odd, we catch it early and return 0.
• Zeroes in input: As noted, if n = 0, the inner loop will execute for all valid t, updating dp[t] += dp[t - 0], effectively doubling the count (since a 0 can be either +0 or -0).

Where this goes next

• Partition Equal Subset Sum — the same knapsack asking whether rather than how many. 4.23.12.
• Last Stone Weight II — minimise the difference between two groups, which is subset sum nearest total / 2.
• Ones and Zeroes — a knapsack with two capacities, so the table gains a dimension.

The habit worth taking: before writing any DP, spend thirty seconds asking whether the problem can be rewritten into one you already know. The algebra here turned a sign-assignment problem into a subset count, and that reduction is worth more than any implementation detail.

What the interviewer will push on

"Derive the reduction." Two equations, add them, the negative group cancels. Do it on the board — it is short and it is the answer they want.

"What are the impossibility checks?" Odd parity, and a target larger than the total.

"Why does the inner loop go down?" Each number gets one sign, so it is used once.

"What do zeros do?" They double the count, and the code handles it with no special case.

"What if you could not find the reduction?" The running-sums dictionary, same complexity.

One thing to volunteer: point out the zero case before being asked. It is the input most likely to break a solution that special-cases things, and noticing that the plain code already handles it shows you traced it.

Next: 4.24.6 Interleaving String — a two-string grid where the third string is read off the coordinates.