LeetCode 494 · 2-D DP

Target Sum, explained with a picture

Plus or minus: walking a number line.

Medium2-D DP
▶ Watch it step by step

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

  1. Find the waste. After using the first i numbers, the signs only matter through the running sum. The choices +1 -1 +1 and -1 +1 +1 both give 1, and everything that follows is the same for both.
  2. Group walks by position. Imagine walking on a number line from 0. Keep a dictionary ways that maps each reachable position to how many different walks end there.
  3. Process one number at a time. For each x, every position total with count w sends all w walks to total + x and all w to total - x. These go into a fresh dictionary nxt, because the old counts must not change while you read them.
  4. Add, never overwrite. Two different old positions can reach the same new position, so the counts are added with +=. A defaultdict(int) supplies the starting 0.
  5. 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

ApproachTimeSpace
Brute forceO(2^n): every sign choice is followed to the endO(n): recursion depth
Dictionary of sums (shown code)O(n × S): each number touches every reachable sum, and S ≤ 2 × total + 1 ≤ 2001O(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 a NameError.
  • 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 +0 and -0 are 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 ways in place while iterating over it, which raises an error or mixes old and new sums.
  • Using = instead of += when filling nxt, 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 raises KeyError when the target is unreachable.
Your turn: can the target be reached at all?

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.

Check what stuck

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?

2. Why is the shown code far faster than trying all 2^n sign choices for n = 20 and sum ≤ 1000?

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?

Score 60% or more and the lesson is marked complete.