416. Partition Equal Subset Sum (Medium)

Problem

Given a non-empty array nums of positive integers, determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example

• nums = [1, 5, 11, 5] → true ([1, 5, 5] and [11])
• nums = [1, 2, 3, 5] → false

LeetCode 416 · 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: Brute force, enumerate subsets

Try every subset; test whether it sums to total / 2.

Python

def can_partition(nums):
    total = sum(nums)                              # L1: O(n)
    if total % 2:                                  # L2: O(1)
        return False
    target = total // 2                            # L3: O(1)
    def f(i, cur):
        if cur == target:                          # L4: O(1)
            return True
        if i == len(nums) or cur > target:         # L5: O(1)
            return False
        return f(i + 1, cur + nums[i]) or f(i + 1, cur)  # L6: two recursive calls
    return f(0, 0)

TypeScript

function canPartition(nums: number[]): boolean {
    const total = nums.reduce((a, b) => a + b, 0);          // L1: O(n)
    if (total % 2 !== 0) return false;                       // L2: O(1)
    const target = total / 2;                                // L3: O(1)
    function f(i: number, cur: number): boolean {
        if (cur === target) return true;                     // L4: O(1)
        if (i === nums.length || cur > target) return false; // L5: O(1)
        return f(i + 1, cur + nums[i]) || f(i + 1, cur);   // L6: two recursive calls
    }
    return f(0, 0);
}

Swift

final class Solution {
    func canPartition(_ nums: [Int]) -> Bool { let sum = nums.reduce(0, +); if sum % 2 == 1 { return false }; let target = sum / 2; func solve(_ i: Int, _ remaining: Int) -> Bool { if remaining == 0 { return true }; if i == nums.count || remaining < 0 { return false }; return solve(i + 1, remaining) || solve(i + 1, remaining - nums[i]) }; return solve(0, target) }
}

Where the time goes, line by line

Variables: n = len(nums), S = sum(nums) (we target S/2).

Line	Per-call cost	Times executed	Contribution
L1 (sum)	$O(n)$	1	$O(n)$
L2, L3 (parity check)	$O(1)$	1	$O(1)$
L4, L5 (base cases)	$O(1)$	per call	$O(2ⁿ)$
L6 (two recursive calls)	$O(1)$	up to 2ⁿ	$O(2ⁿ)$ ← dominates

Each item is either included or not, producing a full binary recursion tree of depth n. No memoization means identical subproblems are recomputed.

Complexity

• Time: $O(2ⁿ)$, driven by L6 (the binary branching at every element).
• Space: $O(n)$ for the recursion stack.

Approach 2: Top-down memoized

Cache by (i, cur).

Python

from functools import lru_cache

def can_partition(nums):
    total = sum(nums)                    # L1: O(n)
    if total % 2:                        # L2: O(1)
        return False
    target = total // 2                  # L3: O(1)

    @lru_cache(maxsize=None)
    def f(i, cur):
        if cur == target:                # L4: O(1)
            return True
        if i == len(nums) or cur > target:  # L5: O(1)
            return False
        return f(i + 1, cur + nums[i]) or f(i + 1, cur)  # L6: cached calls

    return f(0, 0)

TypeScript

function canPartition(nums: number[]): boolean {
    const total = nums.reduce((a, b) => a + b, 0);          // L1: O(n)
    if (total % 2 !== 0) return false;                       // L2: O(1)
    const target = total / 2;                                // L3: O(1)
    const memo = new Map<string, boolean>();
    function f(i: number, cur: number): boolean {
        if (cur === target) return true;                     // L4: O(1)
        if (i === nums.length || cur > target) return false; // L5: O(1)
        const key = `${i},${cur}`;
        if (memo.has(key)) return memo.get(key)!;
        const result = f(i + 1, cur + nums[i]) || f(i + 1, cur);  // L6: cached calls
        memo.set(key, result);
        return result;
    }
    return f(0, 0);
}

Swift

final class Solution {
    func canPartition(_ nums: [Int]) -> Bool { let sum = nums.reduce(0, +); if sum % 2 == 1 { return false }; let target = sum / 2; var memo: [String: Bool] = [:]; func solve(_ i: Int, _ remaining: Int) -> Bool { if remaining == 0 { return true }; if i == nums.count || remaining < 0 { return false }; let key = "\(i):\(remaining)"; if let v = memo[key] { return v }; let v = solve(i + 1, remaining) || solve(i + 1, remaining - nums[i]); memo[key] = v; return v }; return solve(0, target) }
}

Where the time goes, line by line

Variables: n = len(nums), S = sum(nums) (we target S/2).

Line	Per-call cost	Times executed	Contribution
L1 (sum)	$O(n)$	1	$O(n)$
L2, L3 (parity check)	$O(1)$	1	$O(1)$
L4, L5 (base cases)	$O(1)$	per unique (i, cur)	$O(n · target)$
L6 (recursive calls)	$O(1)$ amortized	n · target unique states	$O(n · target)$ ← dominates

With memoization, each (i, cur) pair is computed at most once. There are n indices and at most target+1 possible cur values, giving n · (target+1) unique states.

Complexity

• Time: $O(n · target)$, driven by L6 (unique state count bounds total work).
• Space: $O(n · target)$ for the memo table plus $O(n)$ for the call stack.

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.

Approach 3: Bottom-up 1-D DP (canonical, optimal space)

dp[s] = True iff some subset of processed items sums to s. Process items one at a time; iterate s from high to low to avoid reusing an item (0/1 knapsack rule).

Python

def can_partition(nums):
    total = sum(nums)                        # L1: O(n)
    if total % 2:                            # L2: O(1)
        return False
    target = total // 2                      # L3: O(1)
    dp = [False] * (target + 1)              # L4: O(target)
    dp[0] = True                             # L5: O(1)
    for x in nums:                           # L6: outer loop, n iterations
        for s in range(target, x - 1, -1):  # L7: inner loop, up to target iterations
            dp[s] = dp[s] or dp[s - x]      # L8: O(1) per cell
    return dp[target]                        # L9: O(1)

TypeScript

function canPartition(nums: number[]): boolean {
    const total = nums.reduce((a, b) => a + b, 0);          // L1: O(n)
    if (total % 2 !== 0) return false;                       // L2: O(1)
    const target = total / 2;                                // L3: O(1)
    const dp = new Array(target + 1).fill(false);            // L4: O(target)
    dp[0] = true;                                            // L5: O(1)
    for (const x of nums) {                                  // L6: outer loop, n iterations
        for (let s = target; s >= x; s--) {                 // L7: inner loop (high to low)
            dp[s] = dp[s] || dp[s - x];                     // L8: O(1) per cell
        }
    }
    return dp[target];                                       // L9: O(1)
}

Swift

final class Solution {
    func canPartition(_ nums: [Int]) -> Bool { let sum = nums.reduce(0, +); if sum % 2 == 1 { return false }; let target = sum / 2; var possible: Set<Int> = [0]; for value in nums { for total in possible.sorted(by: >) where total + value <= target { possible.insert(total + value) } }; return possible.contains(target) }
}

Where the time goes, line by line

Variables: n = len(nums), S = sum(nums) (we target S/2).

Line	Per-call cost	Times executed	Contribution
L1 (sum)	$O(n)$	1	$O(n)$
L4 (allocate dp)	$O(target)$	1	$O(target)$
L6 (outer loop)	$O(1)$	n	$O(n)$
L7, L8 (inner loop + update)	$O(1)$	n × target	$O(n · target)$ ← dominates
L9 (return)	$O(1)$	1	$O(1)$

The double loop visits each of the n items against each of the target possible sums. The high-to-low sweep on L7 is not extra work; it is the same $O(target)$ range traversed in reverse.

Complexity

• Time: $O(n · target)$, driven by L7/L8 (the double loop).
• Space: $O(target)$ for the dp array.

Why iterate from high to low

In 0/1 knapsack, iterating s low-to-high would let an item be included more than once in the same outer iteration. Going high-to-low uses only values that haven’t yet been updated this round, preserving the 0/1 semantics.

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.

Summary

Approach	Time	Space
Naive recursion	$O(2ⁿ)$	$O(n)$
Top-down memo	$O(n · target)$	$O(n · target)$
Bottom-up 1-D DP	$O(n · target)$	$O(target)$

Template for every 0/1 knapsack problem, Target Sum (494), Last Stone Weight II (1049), etc.

Test cases

Python

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

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

def _run_tests():
    assert can_partition([1, 5, 11, 5]) == True   # LeetCode example 1
    assert can_partition([1, 2, 3, 5]) == False   # LeetCode example 2
    assert can_partition([1]) == False             # single element, odd total
    assert can_partition([2, 2]) == True           # single element each side
    assert can_partition([1, 2, 5]) == False       # total=8, target=4, no subset
    assert can_partition([3, 3, 3, 4, 5]) == True  # target=9, subset [3,3,3]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

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

console.assert(canPartition([1, 5, 11, 5]) === true);
console.assert(canPartition([1, 2, 3, 5]) === false);
console.assert(canPartition([1]) === false);
console.assert(canPartition([2, 2]) === true);
console.assert(canPartition([1, 2, 5]) === false);
console.assert(canPartition([3, 3, 3, 4, 5]) === true);
console.log('all tests pass');

Related data structures

• Arrays, DP array indexed by subset sum

Related concepts

• Knapsack Patterns, the choose or skip structure behind capacity, target, and subset states.
• Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.