494. Target Sum (Medium)

Problem

Given an integer array nums and an integer target, assign + or − to each number and return the number of sign assignments whose signed sum equals target.

Example

• nums = [1, 1, 1, 1, 1], target = 3 → 5
• nums = [1], target = 1 → 1

LeetCode 494 · Link · Medium

Approach 1: Recursive, try both signs per element

def find_target_sum_ways(nums, target):
    def f(i, cur):
        if i == len(nums):                              # L1: O(1) base case
            return 1 if cur == target else 0
        return f(i + 1, cur + nums[i]) + f(i + 1, cur - nums[i])  # L2: two recursive calls
    return f(0, 0)

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (base check)	O(1)	once per leaf	O(1) each
L2 (two recursive calls)	O(1) work + 2 calls	every non-leaf call	O(2^n) ← dominates

Every element branches into two sign choices. The call tree is a complete binary tree of depth n with 2^n leaves.

Complexity

• Time: O(2^n), driven by L2 double-branching at every step.
• Space: O(n) recursion depth.

Approach 2: Top-down memoized by (i, cur)

from functools import lru_cache

def find_target_sum_ways(nums, target):
    @lru_cache(maxsize=None)                            # L1: cache decorator
    def f(i, cur):
        if i == len(nums):                              # L2: O(1) base case
            return 1 if cur == target else 0
        return f(i + 1, cur + nums[i]) + f(i + 1, cur - nums[i])  # L3: O(1) with cache
    return f(0, 0)

Where the time goes, line by line

Variables: n = len(nums), S = sum(nums).

Line	Per-call cost	Times executed	Contribution
L1 (lru_cache)	O(1)	1	O(1)
L2 (base check)	O(1)	once per unique (i, cur)	O(n · S) total
L3 (cached calls)	O(1) per call	at most n · (2S+1) unique states	O(n · S) ← dominates

The unique states are (i, cur) where i ranges over n+1 values and cur ranges over [-S, S]. Each state is computed once.

Complexity

• Time: O(n · total_sum), driven by L3 across all unique (i, cur) states.
• Space: O(n · total_sum) for the memo table.

Approach 3: Subset-sum transformation + 1-D DP (canonical)

Let P = positive-signed subset, N = negative-signed. Then P + N = total and P - N = target → P = (total + target) / 2. So: count subsets that sum to P. That’s classic 0/1 subset-sum.

Edge cases: total + target must be even and non-negative.

def find_target_sum_ways(nums, target):
    total = sum(nums)                                   # L1: O(n)
    if (total + target) % 2 or total < abs(target):   # L2: O(1) feasibility check
        return 0
    P = (total + target) // 2                          # L3: O(1) target subset sum

    dp = [0] * (P + 1)                                 # L4: O(P) table init
    dp[0] = 1                                          # L5: O(1) empty subset base case
    for x in nums:                                     # L6: O(n) outer loop over elements
        for s in range(P, x - 1, -1):                 # L7: O(P) inner loop, right-to-left
            dp[s] += dp[s - x]                         # L8: O(1) accumulate ways
    return dp[P]                                       # L9: O(1) answer

Where the time goes, line by line

Variables: n = len(nums), P = (sum(nums) + target) / 2.

Line	Per-call cost	Times executed	Contribution
L1-L5 (init)	O(n) + O(P)	1	O(n + P)
L6+L7 (double loop)	O(1) body	n · P	O(n · P) ← dominates
L8 (DP update)	O(1)	n · P	included above

The right-to-left inner loop (L7) is critical for 0/1 knapsack correctness: it ensures each element is used at most once. If you iterated left-to-right, the same x could be counted multiple times in a single pass.

Complexity

• Time: O(n · P), driven by L6/L7 (the double loop).
• Space: O(P) for the 1-D DP array.

Summary

Approach	Time	Space
Naive sign-enumeration	O(2^n)	O(n)
Top-down memo	O(n · total_sum)	O(n · total_sum)
Subset-sum + 1-D DP	O(n · P)	O(P)

The “convert to subset sum” transformation is a classic move, same technique solves “Last Stone Weight II” (1049).

Test cases

# Quick smoke tests, paste into a REPL or save as test_494.py and run.
# Uses the canonical implementation (Approach 3: subset-sum + 1-D DP).

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (total + target) % 2 or total < abs(target):
        return 0
    P = (total + target) // 2
    dp = [0] * (P + 1)
    dp[0] = 1
    for x in nums:
        for s in range(P, x - 1, -1):
            dp[s] += dp[s - x]
    return dp[P]

def _run_tests():
    # problem statement examples
    assert find_target_sum_ways([1, 1, 1, 1, 1], 3) == 5
    assert find_target_sum_ways([1], 1) == 1
    # edge: target unreachable (parity)
    assert find_target_sum_ways([1, 1], 0) == 2
    # edge: target exceeds total sum
    assert find_target_sum_ways([1, 2], 4) == 0
    # single element, negative target
    assert find_target_sum_ways([1], -1) == 1
    # all zeros
    assert find_target_sum_ways([0, 0, 0], 0) == 8
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Related data structures

• Arrays, DP indexed by running subset sum