Target Sum

PracticeNeetCode ↗LeetCode ↗

Given an array of non-negative integers nums and an integer target, assign a + or - sign to each number so the whole expression evaluates to target. Return how many different sign assignments achieve that.

Example

Key Pointers

• Trying every sign combination is 2ⁿ; the same (index, running total) pair recurs across many different sign paths, which is what memoization exploits.
• The running total is bounded between -sum(nums) and sum(nums), so a dictionary keyed by (index, total) is a compact, effective cache.
• At the last index, a path only counts if its running total lands exactly on target.

Step-by-Step Analysis

1. Define a recursive function dfs(i, total): the number of ways to reach target using nums[i:], given the running total so far.
2. Base case: once i == len(nums), return 1 if total == target, else 0.
3. Recursive case: branch into both signs — dfs(i+1, total + nums[i]) and dfs(i+1, total - nums[i]) — and sum them.
4. Cache each (i, total) result the first time it's computed, and reuse it on repeat visits.
5. Return dfs(0, 0).

Complexity

Time: O(n · range of possible sums) — Space: O(n · range of possible sums)

Code

def findTargetSumWays(nums: list[int], target: int) -> int:
    memo = {}

    def dfs(i: int, total: int) -> int:
        if i == len(nums):
            return 1 if total == target else 0
        if (i, total) in memo:
            return memo[(i, total)]

        memo[(i, total)] = dfs(i + 1, total + nums[i]) + dfs(i + 1, total - nums[i])
        return memo[(i, total)]

    return dfs(0, 0)

Code Explanation

How the solution above works, piece by piece.

1. dfs(i, total) = number of ways to assign signs to nums[i:] so the final total equals target, given the running total so far.
2. At the end (i == len(nums)) there is 1 way if the total matches, else 0.
3. Otherwise try both signs: dfs(i + 1, total + nums[i]) + dfs(i + 1, total - nums[i]).
4. Many sign patterns lead to the same (i, total); memo stores each result so it's computed once.
5. O(n × S) time and space, where S is the range of possible totals, instead of O(2ⁿ).

Visual Walkthrough

Running it on nums = [1, 1, 1, 1, 1], target = 3:

Video Explanation

NeetCode — Dynamic Programming, LeetCode 494