Subsets: Every Prefix Is a Valid Answer

Combination Sum records a path only when the remainder hits zero. Subsets, LeetCode 78, rated Medium, uses the same append-recurse-pop skeleton and throws the remainder away. Every node is an answer. The empty prefix, the prefixes in the middle of the tree, and the leaves that took every remaining element — all of them are subsets. That is the whole property.

The trap is to treat this as Partition Equal Subset Sum. That problem asks whether one subset hits a target. Subsets asks you to list every subset. One is a boolean. The other is a search tree whose nodes you snapshot.

The Problem

Given distinct integers nums, return every possible subset. The output is the power set: 2^n lists, including the empty list. Order of the subsets, and order inside a subset, does not matter, but [1, 2] and [2, 1] must not both appear.

Input:  nums = [1, 2, 3]
Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

[] is required. A single-element input returns [[], [x]]. An empty input returns [[]].

Recognizing the Backtracking Pattern

Backtracking is depth-first search on an implicit tree of partial answers. Each node is a path — the elements chosen so far — and a start index that says which remaining elements are still legal. At a node you try the next legal choice, recurse, then undo the choice so the sibling can use the same buffer.

Two rules keep the tree from listing the same set twice:

• Record on entry, not only at the leaves. Combination Sum waits for remaining == 0. Generate Parentheses waits for length 2n. Subsets records before the loop, so the current prefix is in the result even if you take nothing else.
• Never go backwards. After you pick nums[i], the next call starts at i + 1. That forbids [1, 2] and [2, 1] as separate leaves. The start index is the same uniqueness trick as Combination Sum. The difference is that reuse is illegal here, so you pass i + 1, not i.

If you restart the loop at index 0 on every call, you generate permutations of every subset. Interviewers watch for that. Saying "I record first, then I pass i + 1" is the sentence that shows you own the problem rather than a template.

The Approach

Keep a shared path and a start index. On every call, snapshot a copy of the path. Then loop from start to the end, append, recurse with i + 1, pop.

Copy on record (path.copy() or list(path)). The buffer keeps mutating. If you append the buffer itself, every result row aliases the same list and ends as [] after the last pop. That bug looks identical to the one in Combination Sum and Path Sum II, and it is the first thing they will scan for.

Do not sort unless the follow-up introduces duplicates. The input values are already distinct; sorting does not change correctness and is not the point of this question.

Python Solution

def subsets(nums: list[int]) -> list[list[int]]:
    """All subsets of distinct nums. Order does not matter."""
    result: list[list[int]] = []
    path: list[int] = []

    def dfs(start: int) -> None:
        result.append(path.copy())  # every node is an answer
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1)              # next index: no reuse
            path.pop()

    dfs(0)
    return result

The pop after each recursive call is the same restore used in Combination Sum. Forget it and every path aliases one mutating buffer.

The include-or-skip form is equivalent. At index i you recurse twice: once after appending nums[i], once without, and you record only when i == len(nums). That version makes the binary choice obvious. The start-index version makes the family resemblance to Combination Sum obvious. Prefer the start-index loop if they just watched you solve Combination Sum; prefer include-or-skip if they asked "take it or leave it" out loud.

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

    def dfs(i: int) -> None:
        if i == len(nums):
            result.append(path.copy())
            return
        dfs(i + 1)              # skip nums[i]
        path.append(nums[i])
        dfs(i + 1)              # take nums[i]
        path.pop()

    dfs(0)
    return result

Same 2^n leaves. The start-index tree records at internal nodes too, so it has the same number of snapshots and a slightly different shape. Do not spend the interview proving they are equal; name both and implement one.

Walkthrough for [1, 2, 3]

Start at start=0, path empty. Record [].

• Pick 1. Recurse at start=1. Record [1].
  • Pick 2. Recurse at start=2. Record [1, 2].
    • Pick 3. Recurse at start=3. Record [1, 2, 3]. Loop is empty. Pop 3.
    • Loop done. Pop 2.
  • Pick 3 from [1]. Recurse at start=3. Record [1, 3]. Pop 3.
  • Pop 1.
• Pick 2 from the root. Recurse at start=2. Record [2].
  • Pick 3. Record [2, 3]. Pop 3.
  • Pop 2.
• Pick 3 from the root. Recurse at start=3. Record [3]. Pop 3.

Eight snapshots. The permutation [2, 1] was never a node: after picking 2 the start index is 2, so 1 is gone. Draw this if they hand you a marker: a tree of eight nodes, not a list you filter at the end.

Complexity

• Time: O(n · 2^n). There are 2^n subsets and copying a path of length up to n at each of them is O(n). The loop work is a constant factor on the same order. You cannot beat the size of the output.
• Space: O(n) for the path and the call stack, plus whatever the result list occupies. Do not count the output against the algorithm unless they ask you to.

LeetCode keeps nums.length at most 10, so 2^10 is 1024 and the search finishes. The reason to name 2^n is to show you know this is not O(n^2) and not "I will DP a boolean and then reconstruct." Reconstruction of every subset is the output; there is no cheaper structure that still lists them.

The permutation answer they are waiting to reject

# Do not ship this. It lists every order of the same set.
def subsets_permuted(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def dfs() -> None:
        result.append(path.copy())
        for value in nums:            # always from the front
            if value in path:         # uniqueness by value, not by index
                continue
            path.append(value)
            dfs()
            path.pop()

    dfs()
    return result

For [1, 2] this emits [1, 2] and [2, 1]. The start index is what deletes the second one. Membership on the path also quietly assumes values are unique, so it collapses the moment the follow-up allows duplicates. If they ask "why not start at zero," say uniqueness of sets, not "it is slower." Slow is a symptom. Exploring both orders is the cause.

The bitmask cousin is honest and sometimes faster to type:

def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    result: list[list[int]] = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

Same O(n · 2^n). It does not demonstrate backtracking. Offer it if they ask for a second way. Do not start there if the prompt was "use DFS."

Interview Tips and Follow-Ups

• Empty input. nums = [] returns [[]], one subset, not []. The power set of the empty set has one element. If your function returns no rows, you skipped the record-on-entry call.
• Subsets II (LeetCode 90). Values may repeat. Sort first. Recurse with i + 1, and skip a duplicate at the same depth: if i > start and nums[i] == nums[i - 1]: continue. Skipping across depths would drop a valid [1, 1]. The same skip appears in Combination Sum II.
• Permutations (LeetCode 46). Drop the start index. Track a used boolean (or swap in place). Order now matters, so [1, 2] and [2, 1] are both answers.
• Combination Sum (LeetCode 39). Recurse with i, not i + 1, and record only when a remainder hits zero. Subsets is that tree with the remainder removed and the record moved to the top of dfs.
• k-subsets only. Add if len(path) == k as a record filter, or stop the loop once the path is already length k. Combinations (LeetCode 77) is this problem with a size cap.
• Count only, do not list. That is 2^n. If they want the count of subsets that sum to a target, that is Partition Equal Subset Sum or a 0/1 knapsack DP, not this search.

Subsets is Combination Sum with the target stripped out: the uniqueness invariant is still the start index, and the prune is gone because every prefix is legal. Same append-recurse-pop. More of that family sits in the Technical Interview category.