LeetCode 78 · Backtracking · Recursion

Subsets

MediumGenerate every subset — the canonical choose / explore / un-choose pattern.
Given an array of unique integers nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Walkthrough

try:
Every element is either in or out — backtracking explores all 2ⁿ combinations.
nums
1
2
3
current subset
[]
subsets found · 0
decidingin subset
1
function subsets(nums) {
2
  const res = [], path = [];
3
  function backtrack(start) {
4
    res.push([...path]);
5
    for (let i = start; i < nums.length; i++) {
6
      path.push(nums[i]);
7
      backtrack(i + 1);
8
      path.pop();          // undo
9
    }
10
  }
11
  backtrack(0);
◄
12
  return res;
13
}
step 0 / 23
line 11
backtrack(0)
Build subsets by choosing, for each element, whether to include it — depth-first.

Intuition

Each element has exactly two fates: in the subset or out of it. That gives 2ⁿ subsets — and backtracking walks that decision tree.

Carry a running path (the subset built so far). Every state of the path is itself a valid subset, so record it the moment you enter a call — no special base case needed.

Then, for each remaining element, choose it (push), explore deeper (recurse from i + 1 so you never reuse or reorder), and un-choose it (pop).

That pop is the backtrack: it rewinds the path so the next branch starts from a clean state.

The algorithm

  1. 01Start with an empty path and call backtrack(0).
  2. 02On entry, push a copy of the current path into the results.
  3. 03For each index i from start: push nums[i], recurse with i + 1, then pop.
  4. 04The recursion naturally enumerates every include/exclude combination.

Reference implementation

1
function subsets(nums) {
2
  const res = [], path = [];
3
  function backtrack(start) {
4
    res.push([...path]);              // every path is itself a subset
5
    for (let i = start; i < nums.length; i++) {
6
      path.push(nums[i]);             // choose
7
      backtrack(i + 1);               // explore
8
      path.pop();                     // un-choose (backtrack)
9
    }
10
  }
11
  backtrack(0);
12
  return res;
13
}

Complexity

Time
O(n · 2ⁿ) — 2ⁿ subsets, each costing O(n) to copy.
Space
O(n) recursion depth (plus the output).