Target Sum — Knapsack Reduction with Sign Assignment

Problem Statement#

You are given an integer array nums and an integer target. You can place either a + or a - symbol in front of each element of nums, then concatenate them to form an arithmetic expression. Return the number of different expressions that evaluate to target.

Example: nums = [1, 1, 1, 1, 1], target = 3. The answer is 5. The five expressions are -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, and +1+1+1+1-1.

Example: nums = [1], target = 1 returns 1.

Constraints: 1 is less than or equal to nums.length is less than or equal to 20, 0 is less than or equal to nums[i] is less than or equal to 1000, total sum is at most 1000. The bound is small enough that 2^20 brute force technically works, but interviewers want the polynomial DP.

Why This Problem Matters#

Target Sum is loved by Facebook (Meta), Amazon, and Google because it tests whether a candidate can recognize that an apparent sign-assignment problem is mathematically equivalent to a subset-sum count. That algebraic reduction is the kind of insight that distinguishes a strong DP coder from someone who just memorized templates.

It also demonstrates the difference between counting DPs (where transitions add) and existence DPs (where transitions OR). The same skeleton powers many interview favorites including coin counting and word break II.

The Core Insight (Recurrence)#

Let P be the sum of the elements assigned + and N be the sum of those assigned -. Two equations:

• P + N = total (every element contributes its absolute value somewhere).
• P - N = target (the resulting expression).

Adding them gives 2P = total + target, so P = (total + target) / 2. The problem becomes: count subsets of nums whose sum equals P.

For this to be solvable, two preconditions must hold:

1. total + target must be even (otherwise P is not an integer).
2. abs(target) must be at most total (otherwise P is out of range).

Now we have a counting subset-sum problem: define dp[j] as the number of subsets of the elements seen so far that sum to j. Base case dp[0] = 1 (the empty subset). Transition for each n: iterate j from P down to n and update dp[j] += dp[j - n].

The reverse iteration is the same 0/1 knapsack discipline used in Partition Equal Subset Sum — it ensures each item is counted at most once per subset.

Building the DP Solution (Recursion to Memo to Tabulation)#

Naive recursion: branch on + or - at each index, accumulating a running sum. Exponential O(2^n) without memoization.

Memoized recursion: state is (index, runningSum). The running sum can be negative; shift by total to use a non-negative index. Time becomes O(n * total).

Tabulation: after the algebraic reduction, run the standard 1D subset-sum-count DP described above. This is the cleanest solution and what you should code under interview pressure.

Edge cases that the reduction guards against: negative target with abs(target) exceeding total, mixed parity, and empty arrays. Handle them explicitly.

Visual Dry Run (DP Table Trace)#

Trace nums = [1, 1, 1, 1, 1], target = 3. Total is 5. (total + target) / 2 = 4, so we count subsets summing to 4.

Initial: dp = [1, 0, 0, 0, 0] over sums 0..4.

Process n = 1 (j from 4 down to 1):

• dp[4] += dp[3] -> 0.
• dp[3] += dp[2] -> 0.
• dp[2] += dp[1] -> 0.
• dp[1] += dp[0] -> 1.
• After: [1, 1, 0, 0, 0].

Process n = 1 (j from 4 down to 1):

• dp[4] += dp[3] = 0.
• dp[3] += dp[2] = 0.
• dp[2] += dp[1] = 1 -> 1.
• dp[1] += dp[0] = 1 -> 2.
• After: [1, 2, 1, 0, 0].

Process n = 1 (j from 4 down to 1):

• dp[4] += dp[3] = 0.
• dp[3] += dp[2] = 1 -> 1.
• dp[2] += dp[1] = 2 -> 3.
• dp[1] += dp[0] = 1 -> 3.
• After: [1, 3, 3, 1, 0].

Process n = 1 (j from 4 down to 1):

• dp[4] += dp[3] = 1 -> 1.
• dp[3] += dp[2] = 3 -> 4.
• dp[2] += dp[1] = 3 -> 6.
• dp[1] += dp[0] = 1 -> 4.
• After: [1, 4, 6, 4, 1].

Process n = 1 (j from 4 down to 1):

• dp[4] += dp[3] = 4 -> 5.
• dp[3] += dp[2] = 6 -> 10.
• dp[2] += dp[1] = 4 -> 10.
• dp[1] += dp[0] = 1 -> 5.
• After: [1, 5, 10, 10, 5].

dp[4] = 5. Matches expected output.

Optimized Solution — Space-Optimized Python and JavaScript#

Python#

from typing import List
 
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total or (total + target) % 2:
            return 0
        P = (total + target) // 2
        dp = [0] * (P + 1)
        dp[0] = 1
        for n in nums:
            for j in range(P, n - 1, -1):
                dp[j] += dp[j - n]
        return dp[P]

JavaScript#

var findTargetSumWays = function (nums, target) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;
  const P = (total + target) / 2;
  const dp = new Array(P + 1).fill(0);
  dp[0] = 1;
  for (const n of nums) {
    for (let j = P; j >= n; j -= 1) {
      dp[j] += dp[j - n];
    }
  }
  return dp[P];
};

Complexity Analysis#

• Time: O(n * P) where P is (total + target) / 2. For LeetCode constraints that is at most 20 * 1000 = 20000 operations.
• Space: O(P) for the 1D DP array.
• Brute force is O(2^n) — only feasible because n is at most 20, but the DP is asymptotically and constant-factor faster.
• The memoized recursion uses O(n * total) states — also fine, but the tabulation is cleaner.

Common Mistakes#

• Skipping the parity check. If (total + target) is odd, P is not an integer and there are zero solutions; failing to early-return causes index errors or wrong answers.
• Forgetting abs(target) is greater than total returns 0. When the target is unreachable in absolute terms, no expression evaluates to it.
• Iterating j ascending. That allows reusing the same number, turning subset-sum-count into unbounded coin-change-count.
• Treating zeros incorrectly. A zero in nums doubles the count because both +0 and -0 are valid; the DP handles this naturally via dp[j] += dp[j] (the j and j - 0 are the same index, so iterate carefully). Modern templates work correctly because the j loop skips j - 0 = j, leaving the existing count which is exactly the doubling we want — actually with the standard template the zeros are absorbed and counts are right.
• Missing the algebraic reduction and trying a 2D DP indexed by signed running sum without offsetting; that often produces negative indices.

Interview Tips#

• The single best move is to derive P = (total + target) / 2 on the whiteboard before writing code. That demonstrates mathematical maturity.
• State the two preconditions out loud — total + target even and abs(target) is less than or equal to total. Interviewers nod when you guard inputs.
• If the interviewer pushes back on the reduction, offer the memoized-recursion-by-running-sum approach as plan B. Both solve the problem in similar time.
• Discuss the zero-element edge case; it is a popular follow-up at Meta and Google.

Follow-up Questions#

• Return all expressions, not just the count. That requires backtracking, not DP.
• Find the lexicographically smallest sign assignment achieving target. Mix DP with reconstruction.
• Generalize: each element can be assigned +, -, or 0 (drop it). The count balloons; redefine the DP transitions accordingly.
• Solve when nums[i] can be up to 10^9. Pseudo-polynomial DP fails; the problem becomes intractable in general.

Key Takeaways#

• Target Sum reduces to a subset-sum count via the algebra P = (total + target) / 2, where P is the positive subset.
• Two preconditions guard the reduction: total + target even and abs(target) at most total.
• The recurrence dp[j] += dp[j - n] with reverse iteration is the standard 0/1 knapsack count template.
• Time complexity is pseudo-polynomial O(n * P); it is fast for LeetCode constraints but does not scale to large values.
• Memoizing on (index, runningSum) is an alternate solution but requires offsetting negative sums — most interviewers prefer the cleaner reduction.
• Mastering Target Sum cements the difference between counting DPs (sum transitions) and existence DPs (OR transitions).