Target Sum
Problem
Given an integer array nums and an integer target, return the number of ways to assign '+' and '-' signs to each element such that the resulting sum equals target.
- 1 ≤ nums.length ≤ 20
- 0 ≤ nums[i] ≤ 1000
- −1000 ≤ target ≤ 1000
Example
nums = [1,1,1,1,1], target = 35The brute-force approach tries all 2^n combinations of '+' and '-' assignments, which is exponential and inefficient. The optimal approach uses recursion with memoization to avoid redundant calculations. Starting at index 0 with total 0, the algorithm explores two branches: adding nums[0] and subtracting nums[0]. It recursively continues this for each index, accumulating totals. Memoization caches results for each (index, total) pair to prevent recomputation. For example, at index 0 and total 0, it explores total 1 and total -1 at index 1. This branching continues until the end of the array. When index reaches the length of nums, it checks if total equals target; if yes, it counts as 1 way, else 0. Summing all valid ways yields the final answer 5.
Approach
Straightforward Solution
A brute-force approach tries all 2^n sign combinations by recursively exploring '+' and '-' for each element, resulting in exponential time complexity and redundant computations.
Core Observation
The problem asks for counting all possible sign assignments that sum to a target, which naturally forms a decision tree with overlapping subproblems defined by the current index and running total.
Path to Optimal
Recognizing overlapping subproblems, the solution caches results for each (index, total) state using memoization. This pruning avoids recomputing the number of ways for the same state multiple times, reducing the complexity drastically.
Optimal Approach
PreviewUse a top-down recursive function dp(i, total) that returns the number of ways to reach target starting from index i with current sum total. At each step, recursively explore adding and subtracting nums[i]…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n * m)
There are n indices and at most m distinct totals (bounded by sum of nums), each state computed once and cached, resulting in polynomial time.
Space
O(n * m)
Memoization dictionary stores results for each (index, total) pair, which can be up to n times the range of possible totals, leading to O(n*m) auxiliary space.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When counting the number of ways to reach a target with choices at each step, model the problem as a state space defined by index and accumulated total, and cache results to avoid exponential recomputation.
Solution
| 1 | class Solution:
|
| 2 | def findTargetSumWays(self, nums: list[int], target: int) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i, total):
|
| 6 | if i == len(nums):
|
| 7 | return 1 if total == target else 0
|
| 8 | if (i, total) in memo:
|
| 9 | return memo[(i, total)]
|
| 10 |
|
| 11 | add = dp(i + 1, total + nums[i])
|
| 12 | subtract = dp(i + 1, total - nums[i])
|
| 13 |
|
| 14 | memo[(i, total)] = add + subtract
|
| 15 | return memo[(i, total)]
|
| 16 |
|
| 17 | return dp(0, 0) |
Step-by-Step Solution
Initialize Memoization Cache to Store Computed States
| 3 | memo = {}
|
Objective
To create a dictionary that caches the number of ways to reach the target from each (index, total) state.
Key Insight
Memoization is essential to avoid redundant recursive calls. By storing results keyed by (i, total), the algorithm ensures that each unique state is computed once, transforming exponential recursion into efficient dynamic programming.
Interview Quick-Check
Core Logic
Memoization cache keys are tuples of (index, current total), uniquely identifying subproblems.
Common Pitfalls & Bugs
Forgetting to memoize or incorrectly keying the cache leads to exponential time and stack overflow.
Recursively Explore Adding and Subtracting Current Number
To recursively compute the number of ways to reach the target by either adding or subtracting the current number at index i.
Return Final Count from Starting State
To initiate the recursive exploration from index 0 and total 0, returning the total number of valid expressions.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
return 1 if total == target else 0Return 1 if total equals target, else 0, at the base case.
This line correctly counts one valid expression when the accumulated sum matches the target, serving as the foundation for counting all valid paths.
memo = {}Initialize a memoization dictionary to cache results of subproblems.
This cache prevents redundant computations by storing the number of ways to reach the target from each (index, total) state, transforming exponential recursion into polynomial time.
if (i, total) in memo:Check if the current state (index, total) has been computed before.
This memoization lookup avoids recomputing the number of ways for the same state, drastically reducing the recursion tree size.
Full line-by-line criticality + rationale for all 11 lines available on Pro.
Test Your Understanding
Why is memoization necessary in this recursive solution?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Target Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Target Sum drill