Watch 10 video solutions for Target Sum, a medium level problem involving Array, Dynamic Programming, Backtracking. This walkthrough by NeetCode has 232,397 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and 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 <= 1000Problem 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 | 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 |