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

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Recursive, try both signs per element

Python

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)

TypeScript

function findTargetSumWays(nums: number[], target: number): number {
    function f(i: number, cur: number): number {
        if (i === nums.length) return cur === target ? 1 : 0;          // L1: O(1) base case
        return f(i + 1, cur + nums[i]) + f(i + 1, cur - nums[i]);     // L2: two recursive calls
    }
    return f(0, 0);
}

Swift

final class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        func solve(_ index: Int, _ sum: Int) -> Int { if index == nums.count { return sum == target ? 1 : 0 }; return solve(index + 1, sum + nums[index]) + solve(index + 1, sum - nums[index]) }
        return solve(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)

Python

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)

TypeScript

function findTargetSumWays(nums: number[], target: number): number {
    const memo: Map<string, number> = new Map();
    function f(i: number, cur: number): number {
        if (i === nums.length) return cur === target ? 1 : 0;          // L2: O(1) base case
        const key = `${i},${cur}`;
        if (memo.has(key)) return memo.get(key)!;                      // L1: O(1) cache lookup
        const result = f(i + 1, cur + nums[i]) + f(i + 1, cur - nums[i]);  // L3: cached
        memo.set(key, result);
        return result;
    }
    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.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        var memo: [String: Int] = [:]
        func solve(_ index: Int, _ sum: Int) -> Int { if index == nums.count { return sum == target ? 1 : 0 }; let key = "\(index):\(sum)"; if let value = memo[key] { return value }; let value = solve(index + 1, sum + nums[index]) + solve(index + 1, sum - nums[index]); memo[key] = value; return value }
        return solve(0, 0)
    }
}

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.

Python

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

TypeScript

function findTargetSumWays(nums: number[], target: number): number {
    const total = nums.reduce((a, b) => a + b, 0);                    // L1: O(n)
    if ((total + target) % 2 !== 0 || total < Math.abs(target)) return 0;  // L2: feasibility
    const P = (total + target) / 2;                                    // L3: O(1) target sum
    const dp: number[] = new Array(P + 1).fill(0);                    // L4: O(P) table init
    dp[0] = 1;                                                         // L5: O(1) base case
    for (const x of nums) {                                            // L6: O(n) outer loop
        for (let s = P; s >= x; s--) {                                 // L7: O(P) right-to-left
            dp[s] += dp[s - x];                                        // L8: O(1) accumulate
        }
    }
    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.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
        let total = nums.reduce(0,+); guard abs(target) <= total && (total + target) % 2 == 0 else { return 0 }; let desired = (total + target) / 2; var dp = Array(repeating: 0, count: desired + 1); dp[0] = 1
        for number in nums { if number <= desired { for sum in stride(from: desired, through: number, by: -1) { dp[sum] += dp[sum - number] } } }; return dp[desired]
    }
}

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

Python

# 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()

TypeScript

function findTargetSumWays(nums: number[], target: number): number {
    const total = nums.reduce((a, b) => a + b, 0);
    if ((total + target) % 2 !== 0 || total < Math.abs(target)) return 0;
    const P = (total + target) / 2;
    const dp: number[] = new Array(P + 1).fill(0);
    dp[0] = 1;
    for (const x of nums)
        for (let s = P; s >= x; s--)
            dp[s] += dp[s - x];
    return dp[P];
}

console.assert(findTargetSumWays([1, 1, 1, 1, 1], 3) === 5);
console.assert(findTargetSumWays([1], 1) === 1);
console.assert(findTargetSumWays([1, 1], 0) === 2);
console.assert(findTargetSumWays([1, 2], 4) === 0);
console.assert(findTargetSumWays([1], -1) === 1);
console.assert(findTargetSumWays([0, 0, 0], 0) === 8);
console.log("all tests pass");

Related data structures

• Arrays, DP indexed by running subset sum

Related concepts

• Bitmask State, compact-state tactics for representing chosen items, visited sets, and small DP dimensions as integer masks.
• Knapsack Patterns, choose-or-skip DP tactics for capacity, subset, and target-sum problems.
• Memoization, top-down caching tactics for preserving recursive clarity while avoiding repeated subproblem work.