Stage 2: Recursive Thinking·Backtracking

Medium#786 min readBacktrackingBitmaskCascadingLeetCode

Subsets

Backtracking — choose/skip each element

The canonical backtracking template. Include or exclude each element.

Published Apr 16, 2026

Problem

Given a set of distinct integers, return all possible subsets (the power set). The returned list must contain no duplicate subsets; the order of subsets or their elements does not matter.

Input

nums = [1, 2, 3]

Output

[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Input

nums = [0]

Output

[[], [0]]

Intuition

A subset is a binary decision at every element: include it, or don't. With n elements, that's 2ⁿ subsets.

The backtracking frame makes this explicit: walk the array left to right, maintain a "current path", and at each index either append nums[i] and recurse, or skip and recurse. Record the path at every node of the recursion (not just leaves) — each node is a valid subset.

The cascading frame gives a different lens: start with [[]], and for each new element, duplicate every existing subset with the element appended. The sizes go 1 → 2 → 4 → 8, doubling per element. Both approaches produce the same tree, visited in different orders.

Approach

Backtracking (include / skip)

TimeO(n · 2ⁿ)

SpaceO(n)

Recommended

The classic backtracking template. path is shared state; each recursive call records it, then tries each next index — appending, recursing, popping.

The work per subset is O(n) to copy the path into the result, times 2ⁿ subsets.

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut out = Vec::new();
        let mut path = Vec::new();
        fn dfs(start: usize, nums: &[i32], path: &mut Vec<i32>, out: &mut Vec<Vec<i32>>) {
            out.push(path.clone());
            for i in start..nums.len() {
                path.push(nums[i]);
                dfs(i + 1, nums, path, out);
                path.pop();
            }
        }
        dfs(0, &nums, &mut path, &mut out);
        out
    }
}

Rust · runnable

function subsets(nums: number[]): number[][] {
  const out: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number): void => {
    out.push(path.slice());
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  };
  dfs(0);
  return out;
}

TypeScript · runnable

Cascading / iterative

TimeO(n · 2ⁿ)

SpaceO(n · 2ⁿ)

Build the answer left to right. Start with [[]]. For each element, extend every subset in the current answer by appending the new element, and add those extensions to the result.

No recursion, no stack risk. The copying cost is asymptotically the same.

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut out: Vec<Vec<i32>> = vec![vec![]];
        for n in nums {
            let m = out.len();
            for i in 0..m {
                let mut extended = out[i].clone();
                extended.push(n);
                out.push(extended);
            }
        }
        out
    }
}

Rust · runnable

function subsets(nums: number[]): number[][] {
  const out: number[][] = [[]];
  for (const n of nums) {
    const m = out.length;
    for (let i = 0; i < m; i++) {
      out.push([...out[i], n]);
    }
  }
  return out;
}

TypeScript · runnable

Bitmask enumeration

TimeO(n · 2ⁿ)

SpaceO(1) extra

Enumerate mask from 0 to 2ⁿ − 1. The bits of mask say which elements to include.

Compact and great for small n (≤ 20). The constant factor is the lowest of the three approaches.

impl Solution {
    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let n = nums.len();
        (0..(1u32 << n))
            .map(|mask| {
                (0..n).filter(|i| (mask >> i) & 1 == 1).map(|i| nums[i]).collect()
            })
            .collect()
    }
}

Rust · runnable

function subsets(nums: number[]): number[][] {
  const n = nums.length;
  const out: number[][] = [];
  for (let mask = 0; mask < 1 << n; mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(nums[i]);
    }
    out.push(subset);
  }
  return out;
}

TypeScript · runnable

Trace

Backtracking on nums = [1, 2, 3] — the recursion tree (each node emits its path):

                []
          /     |      \
        [1]    [2]     [3]
      /   \     |
   [1,2] [1,3] [2,3]
     |
  [1,2,3]

step	start	path	emitted
enter	0	[]	[]
loop i=0	1	[1]	[1]
loop i=1	2	[1,2]	[1,2]
loop i=2	3	[1,2,3]	[1,2,3]
pop / loop i=2	3	[1,3]	[1,3]
pop / i=1	2	[2]	[2]

Eight subsets emitted in total; the order depends on the approach chosen.

Edge cases

Empty input — the only subset is []; all approaches handle it naturally.
Single element — two subsets: [] and [x].
n > 20 — the bitmask approach overflows 32-bit; use the recursive version (and accept the 2ⁿ cost).

Takeaway

Backtracking has a single template — record-state, loop-over-choices, recurse, undo. Everything in the track (#46 permutations, #39 combination sum, #131 palindrome partitions, #51 n-queens) is a variation on what you emit, what choices are legal at each step, and when you prune. Internalize subsets first — the rest are specializations.

Medium#46

Permutations

Backtracking with a ‘used’ set. Draw the decision tree.

Medium#39

Combination Sum

Unbounded choices. How do you avoid duplicates?

Medium#131

Palindrome Partitioning

Backtrack on where to cut. Precompute palindrome checks with DP.