Target Sum

Problem

You are given an integer array nums and an integer target. You want to build an expression by adding '+' or '-' before each integer in nums. Return the number of different expressions that evaluate to target.

Examples

The brute-force approach

Try all 2^n combinations of + and - assignments. Count those that sum to target.

count = 0
def dfs(i, current):
    nonlocal count
    if i == len(nums):
        if current == target:
            count += 1
        return
    dfs(i+1, current + nums[i])
    dfs(i+1, current - nums[i])
dfs(0, 0)
return count

O(2^n) — exponential.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

If you track all reachable sums and their way-counts as a dictionary, how does processing one more number update that dictionary?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.