Subsets (Backtracking)

Interview Prep

StandardBacktrackingbacktrackingrecursion

The problem

Given an array of distinct integers, return all 2ⁿ possible subsets, in any order.

Pattern: backtracking template

Subsets is the canonical backtracking warm-up. The decision at each step is "should this element be included in the current subset?". The skeleton — append to path, recurse, pop — is the same skeleton you'll use for permutations, combinations, combination sum, n-queens, sudoku, word search, and dozens more. Get this one into your fingers.

Every node in the recursion tree is a valid subset (we append(path.copy()) on entry, not at leaves). This is what makes Subsets different from Permutations or Combination Sum, where we only emit at the leaf.

Backtracking solution

def subsets(nums: list[int]) -> list[list[int]]:
    out, path = [], []
    def back(i: int):
        out.append(path.copy())          # every prefix-of-decisions is itself a valid subset
        for j in range(i, len(nums)):
            path.append(nums[j])
            back(j + 1)
            path.pop()                   # undo for the next branch
    back(0)
    return out

Trace

nums = [1, 2, 3]

back(0, path=[]):    out += [[]]
  j=0: path=[1], back(1):    out += [[1]]
    j=1: path=[1,2], back(2):    out += [[1,2]]
      j=2: path=[1,2,3], back(3):    out += [[1,2,3]]. no children.
      pop -> [1,2]
    pop -> [1]
    j=2: path=[1,3], back(3):    out += [[1,3]]. no children.
    pop -> [1]
  pop -> []
  j=1: path=[2], back(2):    out += [[2]]
    j=2: path=[2,3], back(3):    out += [[2,3]]. no children.
    pop -> [2]
  pop -> []
  j=2: path=[3], back(3):    out += [[3]]. no children.
  pop -> []

result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Alternative: bitmask enumeration

For small n (≤ ~20), every subset corresponds to an n-bit mask. Iterating 0..2^n − 1 and selecting the elements whose bits are set gives the same answer in one pass. Often the cleanest code; doesn't generalize to "decisions with more than two choices".

def subsets_bitmask(nums):
    """For small n (~20), iterate all 2^n bitmasks."""
    n = len(nums)
    return [
        [nums[i] for i in range(n) if mask & (1 << i)]
        for mask in range(1 << n)
    ]

Alternative: iterative doubling

The subsets of nums + [x] are exactly the subsets of nums, plus each of those with x appended. Start with [[]] and grow.

def subsets_iterative(nums):
    """Build by doubling: subsets(nums + [x]) = subsets(nums) ∪ {s+[x] for s in subsets(nums)}."""
    out = [[]]
    for x in nums:
        out += [s + [x] for s in out]
    return out

Complexity

Time: O(n · 2^n) — there are 2^n subsets, each up to length n to write out.
Space: O(n · 2^n) output. Recursion stack O(n).

Variations worth knowing

Subsets II (duplicates): sort the input and inside the for-loop skip nums[j] == nums[j − 1] on sibling branches (but allow descending into them when j == i). Suppresses duplicate subsets.
Permutations: swap "for j in i..n" for "for each unused element". Emit only at leaves.
Combinations C(n, k): add an early return when len(path) == k (and emit there, not at the root).
Combination Sum: at each step add an element and recurse with the same i (reuse allowed). Prune when remaining target goes negative.
Power-set in lex order: the bitmask enumeration gives a specific natural order; the backtracking version gives a DFS order.