Target Sum: From Brute Force to Subset Sum DP

You are given an array of non-negative integers and a target value. Your job is to assign either a + or - sign to each number so that the resulting expression equals the target. Return the number of different ways you can do this.

This is LeetCode 494: Target Sum, and at first glance it looks like a backtracking problem. You could enumerate all 2^n sign assignments and count the valid ones. That works, but it is slow. The real power move is recognizing that this problem reduces to a subset sum counting problem, which you can solve with a 1D DP array in O(n * sum) time.

The brute force: recursion over all assignments

The most direct approach is to try every combination of + and - for each number. At index i, you branch into two choices: add nums[i] or subtract nums[i]. When you reach the end of the array, check if the running sum equals the target.

def find_target_sum_ways(nums, target):
    def helper(i, current_sum):
        if i == len(nums):
            return 1 if current_sum == target else 0
        return (
            helper(i + 1, current_sum + nums[i]) +
            helper(i + 1, current_sum - nums[i])
        )

    return helper(0, 0)

This generates 2^n paths in the recursion tree. For an array of 20 elements, that is about a million calls. For the LeetCode constraint of n up to 20 this would technically work, but there is a much better way. And if the constraint were larger, brute force would not stand a chance.

The key insight

Here is the algebraic trick that transforms this into a subset sum problem. Split the numbers into two groups: let P be the subset of numbers that get the + sign, and let N be the subset that get the - sign.

You know two things:

• P - N = target (that is the goal)
• P + N = total (every number is in one group or the other)

Add these two equations together:

2P = target + total, so P = (target + total) / 2

That changes the entire problem. Instead of searching for sign assignments, you are now asking: how many subsets of nums sum to exactly (target + total) / 2? That is a classic subset sum counting problem, solvable with 0/1 knapsack DP.

Before you build the DP table, check two early-exit conditions:

1. If target + total is odd, there is no way to form an integer subset sum. Return 0.
2. If abs(target) is greater than total, no assignment of signs can reach the target. Return 0.

The solution

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (target + total) % 2 != 0 or abs(target) > total:
        return 0

    p = (target + total) // 2
    dp = [0] * (p + 1)
    dp[0] = 1

    for num in nums:
        for j in range(p, num - 1, -1):
            dp[j] += dp[j - num]

    return dp[p]

The structure is the same as Partition Equal Subset Sum, but instead of tracking reachability (boolean), you are counting the number of ways (integer). dp[j] represents the number of subsets from the elements processed so far that sum to exactly j.

For each number num, you iterate j from p down to num. The backward loop ensures each element is used at most once per subset, which is the 0/1 knapsack constraint. At each cell, dp[j] += dp[j - num] says: "the number of ways to reach sum j increases by the number of ways to reach j - num (then adding this element fills the gap)."

Starting with dp[0] = 1 is crucial. It represents the empty subset, which is the only way to achieve sum 0. Every other subset sum is built on top of this base case.

The backward loop direction matters just as much here as in Partition Equal Subset Sum. If you iterated forward, you would count configurations where the same element is used multiple times. Going right to left ensures each element is considered exactly once.

Complexity analysis

Where P = (target + total) / 2. For the LeetCode constraints (n up to 20, each value up to 1000), P can be at most 10,000. That gives at most 200,000 operations for the DP solution, which runs in microseconds.

The building blocks

This problem is a direct application of the 0/1 knapsack counting pattern. The same structure appears in several related problems:

• Partition Equal Subset Sum: asks whether a subset summing to total / 2 exists (boolean version of the same DP).
• Ones and Zeroes: extends the idea to a 2D knapsack with two resource budgets.
• Coin Change: uses the forward loop instead (unbounded knapsack), which is the contrast that makes the backward loop click.

The core DP state is always the same: dp[j] tracks something about "sum j using elements seen so far." What changes across problems is whether you are tracking a boolean, a count, or a maximum, and whether the loop goes forward (reuse allowed) or backward (no reuse).

Edge cases to watch for

• (target + total) is odd: impossible to split into two integer groups. Return 0 immediately.
• abs(target) exceeds total: even putting all signs as + or all as - cannot reach the target. Return 0.
• Zeros in the array: a zero can be assigned + or - and contributes nothing either way. Each zero doubles the count. For example, nums = [0, 0, 1], target = 1 has 4 ways because each zero independently takes + or - without affecting the sum. The DP handles this correctly because dp[j] += dp[j - 0] means dp[j] += dp[j], which doubles the value.
• All zeros: if every element is 0 and target is 0, the answer is 2^n (every sign assignment is valid).
• Target equals total: only one valid assignment (all positive signs). P = total, and the only subset summing to total is the entire array.

From understanding to recall

The algebraic reduction from "assign +/- signs" to "count subsets summing to P" is the kind of trick that is hard to come up with on the spot but easy to remember once you have seen it a few times. The transformation P = (target + total) / 2 is worth drilling until it is automatic.

Once you have the reduction, the actual DP is identical to other subset sum problems you have already seen. That is the power of learning patterns rather than individual problems. You solve Target Sum by recognizing it as a wrapper around a building block you already know.

Related posts

• Partition Equal Subset Sum - The boolean version of subset sum DP. Same backward loop, same 0/1 knapsack structure, different question (reachability vs counting).
• Coin Change - Unbounded knapsack with a forward loop. The contrast with Target Sum's backward loop clarifies when each direction applies.
• Combination Sum IV - Counting ordered sequences that sum to a target. Same DP skeleton, different loop nesting because order matters.