Subsets

PracticeNeetCode ↗LeetCode ↗

Given an integer array nums of unique elements, return all possible subsets (the power set), with no duplicate subsets.

Example

Key Pointers

• Every element has two choices at each step — include it or skip it — that binary choice is what backtracking explores.
• The power set has exactly 2ⁿ subsets, so the recursion naturally has 2ⁿ leaves.
• Record a copy of the current path at every recursive call, not just at the end — every partial path is itself a valid subset.

Step-by-Step Analysis

1. Define backtrack(start) that first appends a copy of path to the result.
2. Loop i from start to len(nums): append nums[i] to path, recurse with backtrack(i + 1), then pop to undo the choice.
3. Call backtrack(0) to start the search.
4. Return the collected result once the recursion finishes.

Complexity

Time: O(n · 2ⁿ) — Space: O(n) recursion depth, excluding output

Code

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    path = []

    def backtrack(start: int) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Code Explanation

How the solution above works, piece by piece.

1. path is the subset being built; result collects copies of it.
2. result.append(path[:]) at the start of every call: every partial choice is itself a valid subset. path[:] copies it, since path keeps changing.
3. for i in range(start, len(nums)): only pick elements after the last one chosen. This fixes an order and prevents duplicates like [1, 2] and [2, 1].
4. Choose (append), explore (backtrack(i + 1)), un-choose (pop): the standard backtracking pattern.
5. 2ⁿ subsets, each copied in O(n): O(n · 2ⁿ) time.

Visual Walkthrough

The recursion tree for nums = [1, 2, 3]:

Video Explanation

NeetCode — Subsets, LeetCode 78