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

Up to 20 numbers, each at most 1,000.

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.

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.