Target Sum

Target Sum looks like a backtracking problem — assign a + or - to every number and count the assignments that hit a target. But brute force explodes to 2^n. The fix is a classic move: collapse all the partial results into a dictionary of running sum → count, so paths that land on the same sum merge instead of branching forever.

The slow way first

The obvious idea: recursion. At each number, branch into the + choice and the - choice, and when you run out of numbers, check whether the running sum equals the target. That is correct, but it visits every one of the 2^n sign combinations — far too slow once nums gets long.

The question to ask: do I really need to keep every path separate? No. Two different sign choices that arrive at the same running sum are interchangeable from here on. So instead of tracking paths, track how many paths reach each sum.

The idea: a dict of running sum to count

Keep a dictionary ways mapping a running sum → how many ways reach it. Start at {0: 1} (one way to have placed nothing: sum 0). For each number, build a fresh dict: every reachable sum s splits into s + num and s - num, and it hands its count to both. When two sums collide they add up, which is exactly what keeps the work polynomial instead of exponential.

After processing all numbers, the answer is just ways[target] — the number of sign assignments whose total equals the target.

Walk through it

Step through the animation. The pointer num scans the five 1s. Under it, ways grows row by row like Pascal's triangle: {0:1} → {1:1, -1:1} → {2:1, 0:2, -2:1} → and so on. By the last number the dict is {5:1, 3:5, 1:10, -1:10, -3:5, -5:1}, and reading off the entry for sum 3 gives 5.

Pseudocode

ways = {0: 1}                       # one way to reach sum 0 before placing anything
for each num in nums:
    nxt = empty dict
    for each (sum, count) in ways:
        add count into nxt[sum + num]   # choose +num
        add count into nxt[sum - num]   # choose -num
    ways = nxt
return ways.get(target, 0)          # how many assignments land on target

The Python solution

def find_target_sum_ways(nums, target):
    ways = {0: 1}
    for num in nums:
        nxt = {}
        for s, cnt in ways.items():
            nxt[s + num] = nxt.get(s + num, 0) + cnt
            nxt[s - num] = nxt.get(s - num, 0) + cnt
        ways = nxt
    return ways.get(target, 0)

• ways maps a running sum → number of sign assignments that reach it; it begins at {0: 1}.
• For each num we build a fresh nxt so the splits of this round do not interfere with each other.
• Lines 6 and 7 are the heart: every existing sum s contributes its cnt to both s + num (a + choice) and s - num (a - choice).
• nxt.get(s + num, 0) lets colliding sums accumulate instead of overwriting — that merging is what avoids the exponential blowup.
• After the loop, ways.get(target, 0) is the count of assignments equal to the target (0 if it is unreachable).

Complexity

Each number sweeps the current dict of distinct sums, and the number of distinct sums is bounded by the total range of values (roughly 2 · sum(nums) + 1). That turns an exponential search into a polynomial sweep.

When this pattern shows up

Practice