Target Sum
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.
This relationship leads directly to the most efficient approach. We start with the brute force and build up to it.
Key Constraints:
1 <= nums.length <= 20: With n up to 20, an O(2^n) brute force is feasible. 2^20 is about 1 million, which runs within typical time limits.0 <= nums[i] <= 1000and0 <= sum(nums[i]) <= 1000: The total sum is bounded by 1000, so the range of achievable sums is [-1000, 1000]. This bounded range makes a DP over sum values practical.-1000 <= target <= 1000: The target can be negative, so the DP must handle negative running sums (offset them, or use a hash map keyed on the sum).
Approach 1: Brute Force (Recursion)
Intuition
Try every possible assignment. For each element, there are two choices: add it or subtract it. We recursively explore both branches and count how many paths produce the target sum.
This forms a binary tree of decisions. At level 0 we decide the sign for nums[0], at level 1 the sign for nums[1], and so on. Each leaf represents one complete assignment, and we check whether 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.
This explores all 2^n sign assignments, but many different paths reach the same (index, sum) state. Caching the result of each state lets us avoid solving 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).
Memoization tracks sums in the range [-totalSum, +totalSum]. A mathematical transformation converts this into a standard subset sum problem that deals only with non-negative values, which allows an even smaller DP.
Approach 3: Optimal (Subset Sum DP)
Intuition
A mathematical transformation reduces this problem to subset sum counting. Divide the elements into two groups: the positive group P (elements with a + sign) and the negative group N (elements with a - sign). Two facts hold:
P - N = target(the expression must equal target)P + N = totalSum(every element is in one group)
Adding these two equations gives 2P = target + totalSum, so P = (target + totalSum) / 2.
The task becomes counting the subsets of nums that sum to (target + totalSum) / 2, a standard subset sum counting problem solvable with a 1D DP.
Two checks come first. If target + totalSum is odd, P would not be an integer, so no valid assignment exists and the answer is 0. If target + totalSum is negative, P would be negative, which is also impossible, so the answer is 0.
Choosing which elements get a + sign fully determines the expression, since every other element gets a -. So counting sign assignments that reach the target equals counting subsets P whose sum is (target + totalSum) / 2. The 1D array is the 0/1 knapsack counting formulation: for each item we either include it in the subset or not, accumulating the number of ways to reach each sum.
The right-to-left iteration is what keeps each element single-use. When we compute dp[s] += dp[s - num], the value dp[s - num] must still reflect the state before the current num was added. Iterating sums from high to low guarantees dp[s - num] has not yet been updated in this pass, so no subset counts the same element twice.
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.