78. Subsets (Medium)

Problem

Given an integer array nums of distinct elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets; order doesn’t matter.

Example

• nums = [1, 2, 3] → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
• nums = [0] → [[], [0]]

LeetCode 78 · 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).

Go

▶ Run Go ↻ 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 Go to execute. Runs via the Go Playground API.

Approach 1: Bitmask enumeration

There are 2^n subsets; enumerate them by treating i in [0, 2^n) as a bitmask over the input.

def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):                          # L1: 2^n iterations
        subset = [nums[i] for i in range(n) if mask & (1 << i)]  # L2: O(n) per mask
        result.append(subset)
    return result

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$ overhead	2^n	$O(2^n)$
L2 (build subset)	$O(n)$	2^n	$O(n · 2^n)$ ← dominates

Complexity

• Time: $O(n · 2^n)$, driven by L2 scanning bits for each mask.
• Space: $O(n · 2^n)$ output.

Simple and fast for small n. Struggles past n ≈ 20.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func subsets(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        for mask in 0..<(1 << nums.count) { var subset: [Int] = []; for index in nums.indices where mask & (1 << index) != 0 { subset.append(nums[index]) }; result.append(subset) }
        return normalized(result)
    }
}

Approach 2: Iterative build (grow by appending each element)

Start with [[]]; for each element, duplicate every existing subset and add the element to the duplicates.

def subsets(nums):
    result = [[]]
    for x in nums:                                       # L1: n iterations
        result += [s + [x] for s in result]             # L2: O(|result| · k) per step
    return result

Where the time goes, line by line

Variables: n = len(nums), k = average subset length.

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$ overhead	n	$O(n)$
L2 (extend result)	$O(2^i · i)$ at step i	n steps	$O(n · 2^n)$ ← dominates

At step i, result has 2^i entries and we copy each to produce 2^i new ones. Total work is the sum over i from 0 to n-1 of 2^i · i = $O(n · 2^n)$.

Complexity

• Time: $O(n · 2^n)$.
• Space: $O(n · 2^n)$.

Elegant, especially in Python. Slightly more allocation than the backtracking version.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func subsets(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = [[]]
        for value in nums { result += result.map { $0 + [value] } }
        return normalized(result)
    }
}

Approach 3: Backtracking with include/exclude (canonical)

At each index, choose to include or exclude the current element. Record the path at every recursive call (it’s already a valid subset).

Python

def subsets(nums):
    result = []
    path = []

    def backtrack(i):
        if i == len(nums):
            result.append(path[:])    # L1: O(n) copy at leaf
            return
        # exclude
        backtrack(i + 1)              # L2: recurse without nums[i]
        # include
        path.append(nums[i])          # L3: O(1) push
        backtrack(i + 1)              # L4: recurse with nums[i]
        path.pop()                    # L5: O(1) pop

    backtrack(0)
    return result

TypeScript

function subsets(nums: number[]): number[][] {
    const result: number[][] = [];
    const path: number[] = [];

    function backtrack(i: number): void {
        if (i === nums.length) {
            result.push([...path]);    // L1: O(n) copy at leaf
            return;
        }
        // exclude
        backtrack(i + 1);             // L2: recurse without nums[i]
        // include
        path.push(nums[i]);           // L3: O(1) push
        backtrack(i + 1);             // L4: recurse with nums[i]
        path.pop();                   // L5: O(1) pop
    }

    backtrack(0);
    return result;
}

Go

func subsets(nums []int) [][]int {
    result := [][]int{}
    path := []int{}

    var backtrack func(i int)
    backtrack = func(i int) {
        if i == len(nums) {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp) // L1: O(n) copy at leaf
            return
        }
        // exclude
        backtrack(i + 1)              // L2: recurse without nums[i]
        // include
        path = append(path, nums[i])  // L3: O(1) push
        backtrack(i + 1)              // L4: recurse with nums[i]
        path = path[:len(path)-1]     // L5: O(1) pop
    }

    backtrack(0)
    return result
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (copy)	$O(n)$	2^n leaves	$O(n · 2^n)$
L2/L4 (recurse)	$O(1)$ dispatch	2^n nodes	$O(2^n)$
L3/L5 (push/pop)	$O(1)$	2^n	$O(2^n)$ ← dominates (L1 ties)

The binary choice (include/exclude) at each of n levels gives exactly 2^n leaves.

Complexity

• Time: $O(n · 2^n)$.
• Space: $O(n)$ recursion + output.

Why path[:]?

We mutate path in place across recursive calls. When we record a subset, we need a snapshot, hence the copy.

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 {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func subsets(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        func search(_ index: Int, _ current: [Int]) { if index == nums.count { result.append(current); return }; search(index + 1, current); search(index + 1, current + [nums[index]]) }
        search(0, []); return normalized(result)
    }
}

Summary

Approach	Time	Space
Bitmask	$O(n · 2^n)$	$O(n · 2^n)$
Iterative build	$O(n · 2^n)$	$O(n · 2^n)$
Backtracking	$O(n · 2^n)$	$O(n · 2^n)$

All three have the same asymptotic complexity (the output itself is $O(n · 2^n)$). The backtracking template is the one that generalizes to Subsets II (with duplicates) and other tree-of-choices problems.

Test cases

Python

def subsets(nums):
    result = []; path = []
    def backtrack(i):
        if i == len(nums):
            result.append(path[:])
            return
        backtrack(i + 1)
        path.append(nums[i])
        backtrack(i + 1)
        path.pop()
    backtrack(0)
    return result

def _run_tests():
    r = subsets([1, 2, 3])
    assert len(r) == 8
    assert sorted(map(tuple, r)) == sorted([
        (), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)])
    r2 = subsets([0])
    assert sorted(map(tuple, r2)) == [(), (0,)]
    # empty input
    assert subsets([]) == [[]]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function subsets(nums: number[]): number[][] {
    const result: number[][] = [];
    const path: number[] = [];
    function backtrack(i: number): void {
        if (i === nums.length) { result.push([...path]); return; }
        backtrack(i + 1);
        path.push(nums[i]);
        backtrack(i + 1);
        path.pop();
    }
    backtrack(0);
    return result;
}

const norm = (arr: number[][]): string =>
    JSON.stringify(arr.map(a => [...a].sort((x, y) => x - y)).sort((a, b) => JSON.stringify(a) < JSON.stringify(b) ? -1 : 1));

const r = subsets([1, 2, 3]);
console.assert(r.length === 8);
console.assert(norm(r) === norm([[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]));
console.assert(norm(subsets([0])) === norm([[], [0]]));
console.assert(JSON.stringify(subsets([])) === JSON.stringify([[]]));
console.log("all tests pass");

Go

func subsets(nums []int) [][]int {
    result := [][]int{}
    path := []int{}
    var backtrack func(i int)
    backtrack = func(i int) {
        if i == len(nums) {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp)
            return
        }
        backtrack(i + 1)
        path = append(path, nums[i])
        backtrack(i + 1)
        path = path[:len(path)-1]
    }
    backtrack(0)
    return result
}

Related data structures

• Arrays, input; enumeration

Related concepts

• Bitmask State, compact-state tactics for representing chosen items, visited sets, and small DP dimensions as integer masks.
• Recursion, self-similar problem-solving tactics for trees, divide-and-conquer, and search branches.
• Subsets and Combinations, choice-set tactics for generating selected groups while controlling duplicates and order.