Target Sum

1. Problem & Core Objective

Assign + or − to each number so the resulting expression equals target. Return how many assignments achieve it.

nums = [1,1,1,1,1], target = 3   →  5      one minus sign, five places to put it
nums = [1], target = 1           →  1

Constraints: 1 <= nums.length <= 20 · 0 <= nums[i] <= 1000 · 0 <= sum(nums) <= 1000 · -1000 <= target <= 1000

What's actually being tested: an algebraic reduction. Every sign assignment splits the numbers into a positive set P and a negative set N, and a little algebra turns "count sign assignments" into "count subsets summing to a fixed value" — which is Partition Equal Subset Sum with counting.

2. First-Principles Thought Process

The reduction

Let P be the numbers given + and N those given −. Then:

sum(P) − sum(N) = target
sum(P) + sum(N) = total          (every number is in exactly one set)

Adding the two equations:

2 · sum(P) = target + total
sum(P) = (target + total) / 2

So counting sign assignments equals counting subsets P with a fixed sum. That's subset-sum counting — a 0/1 knapsack.

The two rejections that fall out

If target + total is odd, sum(P) isn't an integer, so no assignment works. Return 0.

If |target| > total, the target is unreachable even with all signs aligned. Return 0.

The second matters because (target + total) / 2 could otherwise be negative — target = −10, total = 4 gives −3, and a negative array size throws.

Both are O(1) rejections before any DP.

Why zeros are subtle

A zero can take either sign without changing the sum, so it doubles the assignment count. The subset-counting formulation handles this automatically: dp[s] += dp[s - 0] at s itself, which doubles every reachable count.

That's worth checking rather than assuming — it's the case most likely to reveal an off-by-one in the loop bounds.

The DP

dp[s] = the number of subsets summing to s. Counting, so +:

for (int n : nums)
    for (int s = subsetSum; s >= n; s--)     // DESCENDING — each number once
        dp[s] += dp[s - n];

Descending, because each number is assigned a sign exactly once — 0/1 knapsack, not unbounded.

3. Solution Paths

Approach 1 — Try both signs for every number (brute force)

public int findTargetSumWays(int[] nums, int target) {
    return count(nums, 0, 0, target);
}

private int count(int[] nums, int i, int running, int target) {
    if (i == nums.length) return running == target ? 1 : 0;
    return count(nums, i + 1, running + nums[i], target)
         + count(nums, i + 1, running - nums[i], target);
}

• Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Is 2^20 actually too slow?"

About 10^6 leaves — it passes comfortably at these constraints. So this isn't a timeout objection.

The objection is that the state is (i, running) with only 20 × 2001 = 4 × 10^4 distinct pairs, so it's doing 25× more work than necessary. And it doesn't scale: at n = 40 it would be 10^12.

⭐ "How would you memoise it, given running can be negative?"

Offset the index: memo[i][running + total], where total bounds the range. That gives O(n × total) states.

That offset trick is the general fix for DP over a signed quantity, and it's what the algebraic reduction avoids entirely — by reformulating so the quantity is a non-negative subset sum.

"Which approach would you present?"

Write this first, since it's obviously correct, then show the reduction. The reduction is the interesting part and it's easier to justify once the brute force has made the structure concrete.

Approach 2 — Memoised with an offset

public int findTargetSumWays(int[] nums, int target) {
    int total = 0;
    for (int n : nums) total += n;
    Integer[][] memo = new Integer[nums.length][2 * total + 1];
    return count(nums, 0, 0, target, total, memo);
}

private int count(int[] nums, int i, int running, int target, int total, Integer[][] memo) {
    if (i == nums.length) return running == target ? 1 : 0;
    if (memo[i][running + total] != null) return memo[i][running + total];

    return memo[i][running + total] =
           count(nums, i + 1, running + nums[i], target, total, memo)
         + count(nums, i + 1, running - nums[i], target, total, memo);
}

• Time O(n × total) · Space O(n × total)

Counter-questions on this approach

⭐ "Why Integer[][] rather than int[][]?"

Because 0 is a legitimate answer — plenty of (i, running) states have no completions. With int[][] defaulting to 0, those would be recomputed endlessly.

null is outside the answer domain. Same sentinel discipline as Word Break's Boolean[].

⭐ "Why the + total offset?"

running ranges over [−total, +total], and array indices can't be negative. Shifting by total maps that to [0, 2·total].

It's the standard technique for indexing a signed quantity, and it's exactly what the algebraic reduction sidesteps — by turning the signed running sum into a non-negative subset sum.

"Is the boxing a concern?"

20 × 2001 = 40,020 Integer objects. Fine here, but it's a real cost at scale, and the tabulated version below uses primitives.

Approach 3 — Reduce to subset-sum counting (optimal)

public int findTargetSumWays(int[] nums, int target) {
    int total = 0;
    for (int n : nums) total += n;

    if (Math.abs(target) > total) return 0;          // unreachable even with all signs aligned
    if ((target + total) % 2 != 0) return 0;         // sum(P) would not be an integer

    int subsetSum = (target + total) / 2;

    int[] dp = new int[subsetSum + 1];
    dp[0] = 1;                                        // one way to make 0: the empty subset

    for (int n : nums)
        for (int s = subsetSum; s >= n; s--)          // DESCENDING — each number used once
            dp[s] += dp[s - n];

    return dp[subsetSum];
}

Trace — nums = [1,1,1,1,1], target = 3:

total = 5, subsetSum = (3 + 5) / 2 = 4 — so count subsets summing to 4.

Answer dp[4] = 5 ✓ — matching C(5,4) = 5, which is the binomial check: choose which 4 of the 5 ones get +.

• Time O(n × subsetSum) · Space O(subsetSum)

Counter-questions on this approach

⭐ "Derive the reduction."

Split the numbers into P (given +) and N (given −). Then sum(P) − sum(N) = target and sum(P) + sum(N) = total, since every number is in exactly one set.

Adding them: 2·sum(P) = target + total, so sum(P) = (target + total) / 2.

So each valid sign assignment corresponds to exactly one subset P with that sum — and conversely. Counting assignments therefore is counting subsets, which is 0/1 knapsack.

⭐ "Why both rejection checks, and why in that order?"

(target + total) % 2 != 0 catches a non-integer sum(P).

|target| > total catches an unreachable target — and it must come first (or at least be present), because without it (target + total) / 2 can be negative. With target = −10 and total = 4 that's −3, and new int[−3 + 1] throws NegativeArraySizeException.

So the second check isn't just an optimisation; it prevents a crash.

⭐ "Why does the inner loop descend?"

Because each number is assigned a sign exactly once — it's in P or in N, never both. That's 0/1 knapsack.

Ascending would let dp[s - n] already reflect this same number, counting it twice. Same distinction as Partition Equal Subset Sum versus Coin Change II.

⭐ "How are zeros handled?"

A zero can take either sign without affecting the sum, so it doubles the count. The formulation handles it automatically: with n = 0 the inner loop runs dp[s] += dp[s - 0], doubling every entry.

Worth verifying rather than assuming — with nums = [0,0,1] and target = 1, the answer is 4 (each zero independently + or −), and the DP gives dp[1] = 4.

"Could the count overflow?"

The maximum is 2^20 ≈ 10^6 — the total number of sign assignments. Far inside int.

"Why dp[0] = 1?"

One way to make sum 0: the empty subset. Every counting path bottoms out there.

Comparison

4. Why the Optimal Wins

The brute force passes at n = 20, so this isn't primarily about speed — it's about the reduction.

Turning "count sign assignments" into "count subsets with a fixed sum" removes the signed running total entirely, which is what forces the offset in the memoised version. After the algebra it's a standard 0/1 knapsack count, with O(subsetSum) space rather than O(n × total).

The framing worth keeping:

sum(P) − sum(N) = target and sum(P) + sum(N) = total, so sum(P) = (target + total) / 2. Counting sign assignments is counting subsets with that sum — and both parity and range must be checked, the second to avoid a negative array size.

5. Java Prerequisites

The reduction and its guards

if (Math.abs(target) > total) return 0;        // prevents a negative subsetSum
if ((target + total) % 2 != 0) return 0;       // sum(P) must be an integer
int subsetSum = (target + total) / 2;

0/1 knapsack counting — descending, because each number is signed once:

dp[0] = 1;
for (int n : nums)
    for (int s = subsetSum; s >= n; s--) dp[s] += dp[s - n];

Offset indexing for the memoised alternative — memo[i][running + total] maps [−total, total] to [0, 2·total].

Integer[][] not int[][] for memoisation, since 0 is a valid count.

6. Interview Communication Guide

Clarifying questions: Must every number get a sign (yes — all of them)? Can numbers be 0 (yes — and each zero doubles the count)? Can target be negative (yes — hence the range check)? What's the maximum n (20, so brute force would pass)?

The pitch

"Every sign assignment splits the numbers into a positive set P and a negative set N. That gives two equations: sum(P) − sum(N) = target, and sum(P) + sum(N) = total, since every number is in exactly one set.

Adding them: 2·sum(P) = target + total, so sum(P) = (target + total) / 2.

So counting sign assignments is counting subsets with a fixed sum — a 0/1 knapsack count. That reduction is the whole problem.

Two O(1) rejections fall straight out. If target + total is odd, sum(P) isn't an integer and the answer is 0. And if |target| > total, the target is unreachable — that check isn't just an optimisation, because without it (target + total) / 2 can be negative, and allocating a negative-sized array throws.

Then it's the standard count: dp[s] += dp[s - n], with dp[0] = 1 for the empty subset, and the inner loop descending because each number is signed exactly once. Ascending would be unbounded knapsack, counting a number twice.

Zeros are handled automatically — a zero can take either sign, so it doubles the count, and dp[s] += dp[s - 0] does exactly that. Worth checking rather than assuming: [0,0,1] with target 1 gives 4.

O(n × subsetSum) time, O(subsetSum) space.

The brute force — try both signs recursively — is 2^20 ≈ 10^6 and would actually pass here. But it's 25× more work than the 20 × 2001 distinct states, and memoising it needs an offset because the running sum can be negative. The algebraic reduction avoids that entirely by reformulating in terms of a non-negative subset sum."

Edge cases to volunteer:

Name [0,0,1] and the negative target. The first confirms zeros are counted correctly; the second is where a missing range check produces a negative array size rather than a wrong answer.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the assignments themselves, not the count."

Backtracking — there can be up to 2^n of them, so enumerating is exponential regardless. The DP counts without producing, which is the usual counting-versus-listing gap.

⭐ "What if numbers could be negative?"

The reduction breaks: total is no longer an upper bound on reachable sums, and sum(P) could be negative. You'd fall back to the offset-memoised version, with the index range widened to cover the full reachable interval.

"What if n were 40?"

2^40 brute force is infeasible, but the DP is O(n × subsetSum) and depends on the sum, not n alone — so it scales fine as long as the total stays bounded. That's the pseudo-polynomial nature showing through.

"What if the sum could be 10^9?"

O(subsetSum) becomes infeasible. With small n you'd use meet-in-the-middle at O(2^(n/2)); otherwise it's genuinely hard.

"Count assignments where at most k numbers are negative."

Add a dimension for the negative count: dp[s][j]. O(n × subsetSum × k).

"How does this relate to Partition Equal Subset Sum?"

Directly. That problem asks whether a subset sums to total/2 — which is this reduction with target = 0, and asking existence (||) rather than count (+). Same knapsack, two combiners.