The problem
Put a + or − in front of every number. How many sign choices make the total equal the target?
Input: nums = [1, 1, 1, 1, 1], target = 3 Output: 5
Picture it
Picture walking along a number line, starting at 0. For each number you take a step of that size either right (+) or left (−). We keep, for every position you could be standing on, how many different walks lead there. After using all numbers, read off how many walks end at the target.
How to recognise it
- Every number gets one of two choices (plus or minus), and you want the number of ways to hit an exact total.
- The total after a few numbers depends only on the running sum, not on which signs produced it.
- Different sign choices often land on the same running sum, so their futures are identical.
- The numbers are small (up to 20 numbers, total at most 1000), so the number of distinct sums stays small.
- A count, not a list of the sign choices, is asked for.
Start with brute force
Try both signs for each number and count the complete choices whose total equals the target.
def count_brute(nums, target):
def go(i, total):
if i == len(nums):
return 1 if total == target else 0
return go(i + 1, total + nums[i]) + go(i + 1, total - nums[i])
return go(0, 0)
There are 2^n sign choices, so time is O(2^n) and space is O(n) for the recursion. With n = 20 that is about a million leaves, which is still fine here; the trouble is that every extra number doubles the work. The real limit is that nothing is shared between choices that reach the same sum.
From brute force to the idea
- Find the waste. After using the first i numbers, the signs only matter through the running sum. The choices
+1 -1 +1and-1 +1 +1both give 1, and everything that follows is the same for both. - Group walks by position. Imagine walking on a number line from 0. Keep a dictionary
waysthat maps each reachable position to how many different walks end there. - Process one number at a time. For each
x, every positiontotalwith countwsends allwwalks tototal + xand allwtototal - x. These go into a fresh dictionarynxt, because the old counts must not change while you read them. - Add, never overwrite. Two different old positions can reach the same new position, so the counts are added with
+=. Adefaultdict(int)supplies the starting 0. - Read off the answer. After the last number,
ways.get(target, 0)is the count (0 when the target was never reached).
This is the key idea: merge all sign choices that share a running sum and carry only a count for each sum.
The key idea
DP over sums: a dictionary position → count, updated for each number with ±. O(n × range).
Python solution
def find_target_sum_ways(nums, target):
ways = {0: 1} # total -> number of sign choices
for x in nums:
nxt = defaultdict(int)
for total, w in ways.items():
nxt[total + x] += w
nxt[total - x] += w
ways = nxt
return ways.get(target, 0)LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(2^n): every sign choice is followed to the end | O(n): recursion depth |
| Dictionary of sums (shown code) | O(n × S): each number touches every reachable sum, and S ≤ 2 × total + 1 ≤ 2001 | O(S): one dictionary of counts |
The numbers sum to at most 1000, so no running sum lies outside −1000 … 1000.
Edge cases
- The shown code needs
from collections import defaultdict. Without it you get aNameError. - Target out of reach (
[1]with target 2): returns 0. - Zeros are counted twice:
[0]with target 0 gives 2 and[0, 0, 0]with target 0 gives 8, because+0and-0are different sign choices. - Negative target: symmetric, so
[1, 1, 1, 1, 1]gives 5 for both 3 and −3. - Odd or impossible parity (
[1, 2]with target 0): returns 0, since the sum of all numbers is 3 and has the wrong parity. - Empty list: returns 1 for target 0 (one empty choice) and 0 otherwise, though the problem never gives an empty list.
Common mistakes
- Updating
waysin place while iterating over it, which raises an error or mixes old and new sums. - Using
=instead of+=when fillingnxt, which overwrites counts (see the quiz). - Forgetting the starting entry
{0: 1}, so there are no walks to extend. - Looking up
ways[target]on a plain dictionary, which raisesKeyErrorwhen the target is unreachable.
Same signs, but you only need to answer true or false: is there any choice of signs that gives the target? For [1, 2, 5] the answer is true for 6 and false for 7. Describe your approach, then write it if you like.
Compare with our answer
You no longer need counts, so keep only the set of reachable sums. For each number, every sum splits into two new sums.
def can_reach(nums, target):
sums = {0}
for x in nums:
sums = {t + x for t in sums} | {t - x for t in sums}
return target in sums
can_reach([1, 2, 5], 6) is True (−1 + 2 + 5 = 6), can_reach([1, 2, 5], 7) is False, and can_reach([2, 4], 1) is False. Time O(n × S), space O(S).
A strong answer mentions: replacing the count dictionary with a set, building the new set from the old one, and the same bound on the number of distinct sums.
1. You want to know whether some choice of plus and minus signs on a list of small numbers reaches a target (a yes or no answer). Which approach fits best?
The sums reachable after each number depend only on the earlier sums, so a set grows by at most doubling and merges equal sums. Greedy can overshoot and miss a choice that works later.
2. Why is the shown code far faster than trying all 2^n sign choices for n = 20 and sum ≤ 1000?
Many sign choices end at the same sum, and their counts are merged into one entry. The dictionary is bounded by the range −1000…1000. The code never stops early or skips numbers.
3. A learner changes both update lines to nxt[total + x] = w and nxt[total - x] = w. What does find_target_sum_ways([1, 1, 1, 1, 1], 3) return?
After the second 1, the sum 0 can come from 1 (minus 1) and from −1 (plus 1). With = the second write replaces the first count instead of adding to it, so counts stop growing. Running the variant gives 1 instead of 5.
Score 60% or more and the lesson is marked complete.