Backtracking crash course ↗ · 74

78. Subsets

Every subset is a node in the include/exclude decision tree — record at every level, not just the leaves. A clean backtracking template (push → recurse → pop) generates all 2^n subsets in one DFS pass.

● MediumBacktrackingDecision TreeDFSTypeScript

PROBLEM What we're solving

Given an integer array nums with distinct elements, return all possible subsets (the power set). The solution may be in any order and must contain no duplicate subsets.

Concrete example: nums = [1, 2, 3] → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] — eight subsets total (2^3 = 8).

KEY IDEA Record at every node, not just the leaves

Insight → model the problem as a binary decision tree. At each index you either include the element (go left) or exclude it (go right). Every node in this tree — including the root — is a valid subset. Recording at every recursion entry (before the loop, not after) captures all 2^n subsets with zero extra bookkeeping.

RECIPE Backtrack: push → recurse → pop

  • 0 · Entry point. Call bt(0, []) — start from index 0 with an empty path. Push an empty result immediately (the empty set is always a subset).
  • 1 · Record. At the top of every call, snapshot the current path: result.push([...path]). This captures the subset formed by every element chosen so far, from the empty set to the full set.
  • 2 · Choose. Loop i from start to nums.length - 1. Push nums[i]onto the path (the “include” branch).
  • 3 · Recurse. bt(i + 1, path) — pass i + 1 (not start + 1) so we never revisit earlier elements and avoid producing duplicate subsets.
  • 4 · Un-choose. path.pop()— restore the path for the next iteration (the “exclude” branch). This is the backtrack step.
Classic confusion → passing start + 1 instead of i + 1 in the recursive call. When the loop variable is i (not start), you must pass i + 1 so each deeper level only considers elements to the right of the one just chosen. Using start + 1 produces duplicate subsets because two different iterations could recurse into overlapping index ranges.

COST Complexity

Bit-mask enumeration
O(n · 2^n)
Enumerate all 2^n masks, decode each in O(n).
Backtracking (this approach)
O(n · 2^n)
Same asymptotic; DFS avoids the mask decoding loop — same cost, cleaner code.

Both approaches are optimal — you must output all 2^n subsets and each takes O(n) to copy, so O(n · 2^n) is tight. Space is the same for the call stack (depth n) plus the output.

Pattern transfer → the same push→recurse→pop skeleton drives Combination Sum (record only at leaves, allow repeats), Subsets II (sort + skip duplicates), Permutations(track a “used” boolean array instead of a start index), and Letter Combinations of a Phone Number (characters replace numbers).

RUN IT Decision tree: include or exclude each element

step 0 / 23
STARTBegin backtracking on [1, 2, 3]. We record every node in the decision tree — include or exclude each element.
1▶function subsets(nums: number[]): number[][] {
2▶  const result: number[][] = [];
3 
4  function bt(start: number, path: number[]): void {
5    result.push([...path]);          // record at every node
6 
7    for (let i = start; i < nums.length; i++) {
8      path.push(nums[i]);            // choose: include nums[i]
9      bt(i + 1, path);              // recurse — next index only (no duplicates)
10      path.pop();                    // un-choose: exclude nums[i]
11    }
12  }
13 
14▶  bt(0, []);
15  return result;
16}
102132
State
[]
path
0
result.length
0
start
-
i
-
chosen
0
depth
[]
result[]
just chosen / active indexin current path / depthjust backtrackedrecorded / done
slowfast

TYPESCRIPT The solution, annotated

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

  function bt(start: number, path: number[]): void {
    result.push([...path]);          // record at every node

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);            // choose: include nums[i]
      bt(i + 1, path);              // recurse — next index only (no duplicates)
      path.pop();                    // un-choose: exclude nums[i]
    }
  }

  bt(0, []);
  return result;
}

Reading it block by block

Line 2 — result array. Accumulates every subset. Declared outside the inner function so all recursive calls share the same reference.
Lines 4–12 — the backtracking function bt(start, path). start is the index from which we may still pick elements; path is the subset built so far (mutated in-place for efficiency).
Line 5 — record immediately. result.push([...path]) snapshots the path at the top of every call — before any element is chosen for this level. This is what makes the approach collect every node in the decision tree, not just leaf nodes.
Lines 7–11 — choose / recurse / un-choose. For each remaining index i, push nums[i], recurse with i + 1(forward only), then pop. The pop is the backtrack — it undoes the choice so the loop's next iteration starts from a clean state.
Line 15 — kickoff. bt(0, []) — empty path, start from index 0. The first record call immediately adds the empty subset [].
Complexity → O(n · 2^n) time: there are 2^n subsets and copying each path costs O(n). O(n) space for the call stack (depth at most n) plus O(n · 2^n) for the output itself.

INTERVIEWFollow-ups they'll ask

  • “What if the input contains duplicates?” Sort first, then skip elements equal to the previous one at the same recursion level (Subsets II, LC 90).
  • “Can you do it iteratively?” Start with [[]], then for each number append it to every existing subset and push the new subsets back in. Same O(n · 2^n), no recursion.
  • “How would you generate subsets of a specific size k?” Only record when path.length === k (Combinations, LC 77).
  • “How does this generalize to permutations?” Replace the start index with a boolean used[] array; loop from 0 every time but skip used indices.
  • “What's the bit-mask alternative?” Iterate all integers from 0 to 2^n - 1; bit j set means include nums[j]. Same complexity, simpler to code but harder to adapt when subsets have constraints.

MNEMONIC The one-liner

"Record the path the moment you enter, then push–recurse–pop for every element ahead."

TRIGGERS When you see ___ → reach for ___

"return all possible subsets / power set"backtrack, record at every node
enumerate all include/exclude combosbt(start, path): push→recurse(i+1)→pop
"subsets with duplicates" / sort + skipSubsets II pattern
"all combinations of size k"same skeleton, record only when path.length===k

SKELETON The reusable shape

skeleton.ts
function subsets(nums: number[]): number[][] {
  const result: number[][] = [];

  function bt(start: number, path: number[]): void {
    result.push([...path]);   // record here (every node = valid subset)
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      bt(i + 1, path);
      path.pop();
    }
  }

  bt(0, []);
  return result;
}

FLASHCARDS Tap to flip

Where do you record a subset in the backtracking solution?
At the top of every recursive call, before the loop — result.push([...path]). Every node in the decision tree is a valid subset.
tap to flip
1 / 8
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
Time complexity of backtracking subsets on an array of length n?
QUESTION 02
When does the backtracking function record a subset into the result?
QUESTION 03
Trace nums = [1, 2]. How many subsets are returned?
QUESTION 04
What bug arises from passing start + 1 instead of i + 1 in the recursive call?
QUESTION 05
Which single change transforms the Subsets solution into Combinations (pick exactly k items)?
QUESTION 06
For the iterative approach, what is the starting state?
QUESTION 07
What is the maximum call-stack depth for nums of length n?
QUESTION 08
#78 · SubsetsBuild all 2^n subsets via backtracking: at each index choose to include or exclude the current element and record the partial combination at every level — not only at the leaves.Which algorithmic approach does this primarily use?
QUESTION 09
#78 · SubsetsBuild all 2^n subsets via backtracking: at each index choose to include or exclude the current element and record the partial combination at every level — not only at the leaves.Which implementation correctly solves it?