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
Use 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]. Memoize results keyed by (i, total) to avoid redundant work. The final answer is dp(0, 0).
Time
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
| 5 | def dp(i, total):
|
| 6 | if i == len(nums):
|
| 7 | return 1 if total == target else 0
|
| 11 | add = dp(i + 1, total + nums[i])
|
| 12 | subtract = dp(i + 1, total - nums[i])
|
| 14 | memo[(i, total)] = add + subtract
|
| 15 | return memo[(i, total)]
|
Objective
To recursively compute the number of ways to reach the target by either adding or subtracting the current number at index i.
Key Insight
At each index, the problem branches into two choices: add or subtract the current number. The total number of ways is the sum of ways from both branches. This exhaustive exploration covers all valid sign assignments.
Interview Quick-Check
Core Logic
The recursion explores both adding and subtracting nums[i], summing their results to count all valid expressions.
State & Boundaries
The base case occurs when index reaches the length of nums, returning 1 if total equals target, else 0.
Common Pitfalls & Bugs
Not handling the base case correctly or missing one of the two recursive calls leads to incorrect counts.
Return Final Count from Starting State
| 17 | return dp(0, 0) |
Objective
To initiate the recursive exploration from index 0 and total 0, returning the total number of valid expressions.
Key Insight
Starting from the initial state with no numbers processed and total sum zero, the recursion explores all sign assignments. The returned value represents the total count of expressions evaluating to target.
Interview Quick-Check
Core Logic
The initial call dp(0, 0) triggers the entire memoized recursion tree.
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.
return memo[(i, total)]Return the cached result for the current state if available.
Returning cached results immediately prunes redundant recursive calls, ensuring efficient computation.
memo[(i, total)] = add + subtractStore the sum of both recursive results in the memoization cache.
Caching the combined count for the current state ensures that future calls with the same parameters return instantly, preventing exponential blowup.
def dp(i, total):Define the recursive function dp with parameters index and current total.
This function models the problem as a state space where each state is defined by the current index and accumulated total, enabling systematic exploration of all sign assignments.
if i == len(nums):Check if the recursion has processed all numbers.
Reaching the end of the array is the base case that determines if the current total matches the target, which decides if this path counts as a valid expression.
add = dp(i + 1, total + nums[i])Recursively compute ways by adding nums[i] to the total.
Exploring the branch where the current number is added captures all expressions with a '+' sign at this position.
subtract = dp(i + 1, total - nums[i])Recursively compute ways by subtracting nums[i] from the total.
Exploring the branch where the current number is subtracted captures all expressions with a '-' sign at this position.
return memo[(i, total)]Return the cached total number of ways for the current state.
Returning the memoized result completes the recursion step, propagating counts up the call stack.
return dp(0, 0)Start the recursive exploration from index 0 and total 0.
This initial call triggers the entire memoized recursion, covering all possible sign assignments and returning the final count.
Test Your Understanding
Why is memoization necessary in this recursive solution?
Because without memoization, the recursion explores many overlapping subproblems multiple times, leading to exponential time; memoization caches results for each state to ensure each is computed once, reducing complexity to polynomial.
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