BacktrackingAlgorithmaka power set, all subsets, subset enumeration

Subsets (Power Set)

Enumerate all 2^n subsets of a set by deciding, for each element in turn, whether to include it.

▶ VisualizePattern: BacktrackingPractice (3)
Progress

Overview

The power set of n distinct elements has 2^n members. Two equivalent recursive views generate it: the include/exclude tree (each element makes a binary decision, giving a complete binary tree of depth n) and the start-index tree (at each node, choose the next element from those after the last chosen one, emitting the current path at every node).

The start-index formulation is the workhorse for interview variants — subsets with duplicates, Combinations (n choose k) of size k, combination sum — because it naturally produces each subset in sorted index order exactly once.

backtrackingpower set2^ninclude/excludestart index

Intuition

A mental model before the formal terms.

Lay the elements in a row. Walk left to right; at each element flip a coin: keep or drop. Every sequence of n coin flips is one subset, so there are 2^n of them. Backtracking simply enumerates the flip sequences depth-first.

In the start-index view: the current path is a subset; you extend it by appending any element that lies to the right of the last one. Because you only ever move right, {1,3} is produced once (1 then 3) and never as {3,1}.

How it works

  1. Sort the input if duplicates must be handled; otherwise order is irrelevant.
  2. Call backtrack(start=0, path=[]). On entry, record a copy of path — every node of the tree is a subset.
  3. Loop i from start to n-1: skip i if i > start and a[i] == a[i-1] (duplicate handling); push a[i]; recurse with start = i + 1; pop.
  4. The recursion naturally terminates when start == n (empty loop).

Why it works

Each subset corresponds to a unique increasing sequence of indices. The start-index loop generates exactly the increasing sequences, one per node, so every subset is emitted once and nothing else is.

With sorted input and the a[i] == a[i-1] skip inside the same loop level, the first copy of a value is always the one chosen at that level; choosing a later identical copy would produce a subset already generated via the first copy.

Recognition

How to tell a problem wants this.

  • "Return all possible subsets / combinations / selections" with n ≤ 16 or so.
  • Choosing a subset of items subject to a constraint where you need to enumerate rather than count.
  • The output size is stated to be at most 2^n — the problem is telling you to enumerate.
“all combinations” → Backtracking

Interactive visualization

Play, step, change the input. ← → and space work too.

Call stack (top first)
empty
Subsets found (0 / 8)
empty
1/31Enumerate all subsets of [1, 2, 3]. Each element is either in or out, so there are 2^3 = 8 subsets and the recursion tree is a full binary tree.
Call on the stackCall returnedElement in current subset
PseudocodeLearn Subsets (Power Set) →
1go(i, current):
2  if i == n: record(current); return
3  current.push(a[i]); go(i+1, current)   // include a[i]
4  current.pop()                          // undo (backtrack)
5  go(i+1, current)                       // exclude a[i]
Variables
n3
Complexity
worst O(n · 2^n)
space O(n)
Speed

Pseudocode

1sort(a)
2backtrack(start, path):
3  record(copy of path)
4  for i in start..n-1:
5    if i > start and a[i] == a[i-1]: continue
6    path.push(a[i])
7    backtrack(i + 1, path)
8    path.pop()
9backtrack(0, [])

Implementations

1def subsets(nums: list[int]) -> list[list[int]]:
21 · Sort so equal values are adjacent
3    nums = sorted(nums)
4    out: list[list[int]] = []
5    path: list[int] = []
6 
7    def backtrack(start: int) -> None:
82 · Record current subset
9        out.append(path[:])
10        for i in range(start, len(nums)):
113 · Skip duplicates at this level
12            if i > start and nums[i] == nums[i - 1]:
13                continue
144 · Choose / explore / un-choose
15            path.append(nums[i])
16            backtrack(i + 1)
17            path.pop()
18 
19    backtrack(0)
20    return out
Walkthrough
  1. nums = sorted(nums) rebinds to a new sorted list, leaving the caller's list untouched.
  2. out.append(path[:]) stores a slice copy; path itself is mutated by every frame.
  3. if i > start and nums[i] == nums[i - 1]: continue skips repeated choices at the same depth.
  4. append / backtrack(i + 1) / pop is the standard choose-explore-un-choose triple.
Complexity (this implementation)
time O(n * 2^n) · space O(n) recursion depth plus O(n * 2^n) output

path[:] copies O(n) per subset, which is inherent to producing the output.

Language notes
  • itertools.combinations(nums, k) for k in range(n + 1) generates all subsets lazily; it does not dedupe equal values.
  • Sorting mixed-type lists raises TypeError; the type hint list[int] documents the assumption.
  • Depth is n, far below the default 1000-frame limit for any realistic input.
Common mistakes in this language
  • Appending path instead of path[:] so every result is the same (finally empty) list.
  • Forgetting to sort first when the input has duplicates.
  • Using nums.sort() on the argument, which mutates the caller's list.
Language differences that matter here
  • JS/TS Array.prototype.sort() compares as strings by default; sort((a, b) => a - b) is mandatory for numbers. C++ std::sort and Python sorted order numbers correctly out of the box.
  • Copying the result: C++ out.push_back(path) copies implicitly; JS/TS need [...path]; Python needs path[:]. Pushing the shared reference in JS/TS/Python is the number one bug.
  • C++ passes path/out as references explicitly; the other three capture them in closures.

Complexity

Best
—
Average
—
Worst
O(n · 2^n)
Space
O(n)

There are 2^n subsets and copying each costs up to O(n). Recursion depth is n. Output storage is O(n · 2^n) on top of the O(n) working space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • You must output every subset, or test each subset against a predicate that has no exploitable structure.
  • n ≤ ~20; beyond that 2^n is out of reach and the problem wants Dynamic Programming or Bitmask DP counting instead.
Avoid it when
  • You only need the count of subsets with a property (e.g. sum equals k) — 0/1 Knapsack-style DP counts in O(n · k).
  • n up to 20–25 and you want raw speed over a fixed-size set — Subset Generation with Bitmasks iterates masks with no recursion overhead.

Alternatives

Subset Generation with BitmasksCombinations (n choose k)0/1 Knapsack

Common mistakes

  • Recording path itself instead of a copy.
  • Applying the duplicate skip as i > 0 instead of i > start — that also skips legitimate choices in deeper levels.
  • Forgetting to sort before the duplicate skip, so equal values are not adjacent.
  • Recursing with start + 1 instead of i + 1, which generates the same subset multiple times.

Interview patterns

  • Subsets II (with duplicates): sort + skip.
  • Combination Sum: allow reuse by recursing with i instead of i + 1, prune when running sum exceeds target.
  • Letter combinations / partition problems: the same start-index skeleton where each "element" is a slice of the input.
Interview questions on this
Mock interviews

Example problems

SubsetsmediumCombination SummediumPartition Equal Subset Summedium