Target Sum - Solution & Explanation
Problem Statement
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
- For example, if
nums = [2, 1], you can add a'+'before2and a'-'before1and concatenate them to build the expression"+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1 Output: 1
Constraints:
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
Approach Overview
Problem Overview: You receive an integer array nums and a target value. For every number, you can assign either + or -. The task is to count how many different expressions evaluate to the target. The challenge is avoiding the exponential explosion of sign combinations.
Approach 1: Recursive Backtracking with Memoization (Time: O(n * sum), Space: O(n * sum))
The straightforward idea is to try both choices for every element: add it or subtract it. A plain backtracking solution explores a binary decision tree with 2^n possibilities. Many states repeat, though. The same index and running sum appear multiple times. Store results in a memo table keyed by (index, currentSum). When the recursion revisits the same state, return the cached value instead of recomputing. This converts the exponential search into a pseudo‑polynomial dynamic programming problem where the number of states is bounded by n * totalSumRange. This approach is intuitive in interviews because it mirrors the brute-force reasoning but shows optimization using dynamic programming.
Approach 2: 2D Dynamic Programming Table (Time: O(n * sum), Space: O(n * sum))
A key observation converts the problem into a subset sum. If numbers assigned + sum to P and numbers assigned - sum to N, then P - N = target and P + N = totalSum. Combining them gives P = (target + totalSum) / 2. The problem becomes: count subsets whose sum equals P. Use a DP table where dp[i][s] stores the number of ways to reach sum s using the first i elements of the array. Transition: either include the current number or skip it. Each state accumulates counts from previous rows. This formulation avoids negative sums entirely and follows the classic subset-sum counting pattern used in many interview problems.
Recommended for interviews: Start with the recursive backtracking idea to demonstrate the search space and reasoning. Then introduce memoization to remove repeated work. Many interviewers also expect the subset-sum transformation because it shows strong dynamic programming intuition. Both optimized approaches run in O(n * sum), but the subset-sum DP is often considered the cleanest final solution.
Approach 1: Recursive Backtracking with Memoization
This approach utilizes recursive backtracking to explore all possible combinations of adding '+' or '-' in front of each number. To optimize, we use memoization to cache the results of previously computed states, which reduces recalculations and improves efficiency.
In the Python solution, we define a recursive function backtrack that takes the index of the current number and the total, which is the current calculated sum. We use memoization to store already calculated states, which ensures each recursive path is only computed once. At each step, we decide to either add or subtract the current number, continuing until all numbers are used. The base case checks if the formed expression equals target.
Complexity
Time Complexity: O(n * sum(nums)), where n is the number of elements.
Space Complexity: O(n * sum(nums)) for the memoization storage.
Approach 2: 2D Dynamic Programming Table
This approach utilizes a 2D dynamic programming table. We determine how many ways the numbers can sum to a potential value (positive or negative).
The Java solution initializes a 2D array dp, where dp[i][j] represents the number of ways the first i numbers can add up to j - sum. We initialize dp[0][sum] to 1 to account for starting from zero. We iterate through the numbers, updating the dp table to account for all possible sums achievable by adding or subtracting each number.
Code
Java
JavaScript
Complexity
Time Complexity: O(n * 2 * sum), where n is the number of elements.
Space Complexity: O(n * 2 * sum) due to the DP table storage.
Approach 3: Dynamic Programming
Let's denote the sum of all elements in the array nums as s, and the sum of elements to which we assign a negative sign as x. Therefore, the sum of elements with a positive sign is s - x. We have:
$
(s - x) - x = target \Rightarrow x = \frac{s - target}{2}
Since x geq 0 and x must be an integer, it follows that s geq target and s - target must be even. If these two conditions are not met, we directly return 0.
Next, we can transform the problem into: selecting several elements from the array nums such that the sum of these elements equals \frac{s - target}{2}. We are asked how many ways there are to make such a selection.
We can use dynamic programming to solve this problem. Define f[i][j] as the number of ways to select several elements from the first i elements of the array nums such that the sum of these elements equals j.
For nums[i - 1], we have two choices: to select or not to select. If we do not select nums[i - 1], then f[i][j] = f[i - 1][j]; if we do select nums[i - 1], then f[i][j] = f[i - 1][j - nums[i - 1]]. Therefore, the state transition equation is:
f[i][j] = f[i - 1][j] + f[i - 1][j - nums[i - 1]]
This selection is based on the premise that j geq nums[i - 1].
The final answer is f[m][n], where m is the length of the array nums, and n = \frac{s - target}{2}.
The time complexity is O(m times n), and the space complexity is O(m times n)$.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Approach 4: Dynamic Programming (Space Optimization)
We can observe that in the state transition equation of Solution 1, the value of f[i][j] is only related to f[i - 1][j] and f[i - 1][j - nums[i - 1]]. Therefore, we can eliminate the first dimension of the space and use only a one-dimensional array.
The time complexity is O(m times n), and the space complexity is O(n).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Backtracking with Memoization | Time Complexity: O(n * sum(nums)), where n is the number of elements. |
| 2D Dynamic Programming Table | Time Complexity: O(n * 2 * sum), where n is the number of elements. |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Plain Recursive Backtracking | O(2^n) | O(n) | Conceptual baseline to understand the decision tree of + and - assignments |
| Backtracking with Memoization | O(n * sum) | O(n * sum) | General case when implementing top‑down dynamic programming |
| 2D Dynamic Programming (Subset Sum) | O(n * sum) | O(n * sum) | Preferred interview solution after transforming the problem into subset sum |
Video Solution
DP 21. Target Sum | DP on Subsequences • take U forward • 301,137 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Target Sum easy or hard?
How to solve Target Sum in O(n)?
What is the best approach for Target Sum?
What data structure is used in Target Sum?
What is the time complexity of Target Sum?
Target Sum Python or Java solution approach?
Is Target Sum asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Target Sum with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor