Target Sum
Last Updated: March 28, 2026
Understanding the Problem
We have an array of non-negative integers, and for each number we must assign either a + or - sign. The question is: how many sign assignments produce a total that equals the target?
This is fundamentally a counting problem over all possible subsets. Every element ends up in one of two groups: those with a + sign and those with a - sign. If we call the sum of the positive group P and the sum of the negative group N, we need P - N = target. Since every element must go to one group or the other, we also know P + N = totalSum.
That observation is the key to unlocking the most efficient approach. But let's start simple and build up to it.
Key Constraints:
1 <= nums.length <= 20--> With n up to 20, even O(2^n) is feasible. 2^20 is about 1 million, which runs comfortably within time limits.0 <= nums[i] <= 1000and0 <= sum(nums[i]) <= 1000--> The total sum is bounded by 1000, which means the range of achievable sums is [-1000, 1000]. This bounded range opens the door for DP over sum values.-1000 <= target <= 1000--> Target can be negative, so we need to handle negative indices in our DP or offset them.
Approach 1: Brute Force (Recursion)
Intuition
The most direct approach is to try every possible assignment. For each element, we have two choices: add it or subtract it. We recursively explore both branches and count how many paths produce the target sum.
Think of it as a binary tree of decisions. At level 0, we decide the sign for nums[0]. At level 1, for nums[1]. And so on. Each leaf of this tree represents one complete assignment, and we check if the accumulated sum equals the target.
Algorithm
- Start a recursive function with index 0 and current sum 0.
- At each index, make two recursive calls: one adding
nums[index]and one subtracting it. - When the index reaches the end of the array, check if the current sum equals the target. Return 1 if it does, 0 otherwise.
- Sum up the counts from both branches.
Example Walkthrough
Code
- Time Complexity: O(2^n). At each of the n elements, we branch into two recursive calls, creating a complete binary tree with 2^n leaves.
- Space Complexity: O(n). The recursion depth is n (one level per element), so the call stack uses O(n) space.
We're exploring all 2^n sign assignments, but many different paths reach the same (index, sum) state. What if we cached the result of each state so we never solve the same subproblem twice?
Approach 2: Memoization (Top-Down DP)
Intuition
The brute force has overlapping subproblems. Multiple paths through the decision tree can arrive at the same index with the same running sum. Once we've computed the answer for a particular (index, sum) state, there's no reason to compute it again.
By adding a cache (hash map) that stores the result for each (index, sum) pair, we avoid redundant work. The number of distinct states is bounded by n (2 totalSum + 1), since the sum can range from -totalSum to +totalSum.
Algorithm
- Start a recursive function with index 0 and current sum 0, along with a memo dictionary.
- Before computing, check if
(index, currentSum)is already in the memo. If so, return the cached result. - At each index, make two recursive calls (add and subtract), sum their results, store in memo, and return.
- Base case: when index equals the array length, return 1 if sum equals target, else 0.
Example Walkthrough
Code
- Time Complexity: O(n totalSum). There are at most n (2 * totalSum + 1) distinct states, and each state is computed once.
- Space Complexity: O(n totalSum). The memo stores at most n (2 * totalSum + 1) entries, and the recursion stack is O(n).
The memoization approach tracks sums in the range [-totalSum, +totalSum], but with a mathematical transformation, we can convert this into a standard subset sum problem that only deals with non-negative values.
Approach 3: Optimal (Subset Sum DP)
Intuition
Here's the mathematical insight that transforms this problem. Divide the elements into two groups: the "positive" group P (elements with a + sign) and the "negative" group N (elements with a - sign). We know:
P - N = target(the expression must equal target)P + N = totalSum(every element is in one group)
Adding these two equations: 2P = target + totalSum, so P = (target + totalSum) / 2.
This means we need to find the number of subsets of nums that sum to (target + totalSum) / 2. That's a classic subset sum counting problem, solvable with a clean 1D DP.
There are two quick checks before we proceed: if target + totalSum is odd, no valid assignment exists (P must be an integer), so return 0. If target + totalSum is negative, it's also impossible, so return 0.
The mathematical transformation converts the problem from "assign + or - to each element" into "find subsets summing to a target." This works because choosing which elements get a + sign completely determines the expression (the rest get -). The 1D DP is the classic 0/1 knapsack counting formulation: for each item, we either include it in the subset or not, and we count the number of ways to reach each possible sum.
The right-to-left iteration is critical. By processing sums from high to low, when we compute dp[s] += dp[s - num], the value dp[s - num] still reflects the state before including the current number. This prevents us from counting the same element twice in a single subset.
Algorithm
- Compute
totalSumof all elements. - Check if
(target + totalSum)is non-negative and even. If not, return 0. - Set
subsetSum = (target + totalSum) / 2. - Create a 1D DP array of size
subsetSum + 1, initialized to 0, withdp[0] = 1(one way to make sum 0: take nothing). - For each number in
nums, iterate the DP array from right to left (fromsubsetSumdown tonum), updatingdp[s] += dp[s - num]. - Return
dp[subsetSum].
Example Walkthrough
Code
- Time Complexity: O(n * subsetSum) where subsetSum = (target + totalSum) / 2. We iterate through each of the n elements, and for each one, update at most subsetSum + 1 entries in the DP array.
- Space Complexity: O(subsetSum). The 1D DP array has subsetSum + 1 entries. No recursion stack is needed.