Backtracking: Subsets, Permutations, and Combinations

Every problem that asks for "all possible arrangements" or "all valid subsets" is a backtracking problem. The interviewer might dress it up differently — generate all subsets, list all permutations, find combinations summing to a target — but it's the same underlying mechanism every time.

Backtracking is DFS plus an undo step. You make a choice, explore all consequences of that choice recursively, then undo the choice and try the next one. The implicit structure you're building is a decision tree, and once you can see that tree clearly, the code writes itself.

The Mental Model

Here's the core template that powers almost every backtracking solution:

const backtrack = (start, currentPath) => {
  // Optionally add to results here (at every node, or only at leaves)
  result.push([...currentPath]);
 
  for (let i = start; i < choices.length; i++) {
    currentPath.push(choices[i]);   // Make a choice
    backtrack(i + 1, currentPath);  // Explore consequences
    currentPath.pop();              // Undo the choice
  }
};

Two things to burn into memory:

1. [...currentPath] — always spread when adding to results. currentPath is a reference to the same array that gets mutated. If you push the reference, every result entry will show an empty array by the time recursion finishes.

2. The start parameter — controls which choices are available at each level. Passing i + 1 prevents going backward (no duplicates in different order). Passing i allows reuse of the same element.

Subsets (LeetCode 78)

Given an array of unique integers, return all possible subsets (the power set).

An array of n elements has 2^n subsets. Each element is either in a subset or it isn't — that's the binary choice at each node.

Brute force — bit manipulation:

// Bit mask approach: iterate all 2^n bitmasks
// Time: O(n * 2^n) — for each of the 2^n masks, scan n bits
// Space: O(n * 2^n) for the output
const subsets = (nums) => {
  const result = [];
  const n = nums.length;
 
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) subset.push(nums[i]);
    }
    result.push(subset);
  }
  return result;
};

This works fine and is O(n * 2^n) like backtracking. The downside: it's hard to add constraints. If you later need "only subsets summing to target K," the bitmask version gets messy. Backtracking keeps it clean.

Backtracking:

// Backtracking subsets
// Time: O(n * 2^n) — 2^n subsets, each copy costs O(n)
// Space: O(n) recursion depth, O(n * 2^n) for output
const subsets = (nums) => {
  const result = [];
 
  const backtrack = (start, current) => {
    result.push([...current]); // Every node in the tree is a valid subset
 
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  };
 
  backtrack(0, []);
  return result;
};

The decision tree for [1, 2, 3]:

Notice: when we're at [1] and loop from start = 1, we only see indices 1 and 2 (2 and 3). We never go back to index 0. That's the start parameter doing its job — preventing [2, 1] from appearing alongside [1, 2].

Every node in this tree is added to result. Root is the empty subset. All leaves and interior nodes are valid. That's what makes subsets slightly different from permutations and combinations — there's no "base case" that adds to results; you add at every step.

Permutations (LeetCode 46)

Given an array of distinct integers, return all permutations.

Permutations differ from subsets in one key way: order matters. [1, 2, 3] and [3, 2, 1] are different permutations. Every element must appear in each permutation. There are n! permutations for n elements.

Because order matters, you can't use the start trick — at each position, any unused element is fair game. Instead, track which elements have been used:

// Backtracking with used[] array
// Time: O(n! * n) — n! permutations, copying each takes O(n)
// Space: O(n) recursion depth + O(n) for the used array
const permute = (nums) => {
  const result = [];
  const used = new Array(nums.length).fill(false);
 
  const backtrack = (current) => {
    if (current.length === nums.length) {
      result.push([...current]); // Only leaf nodes are complete permutations
      return;
    }
 
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;      // Skip already-chosen elements
 
      used[i] = true;
      current.push(nums[i]);
      backtrack(current);
      current.pop();
      used[i] = false;            // Undo the used mark
    }
  };
 
  backtrack([]);
  return result;
};

There's an alternate version using in-place swapping that avoids the used[] array:

// Swap-based permutations (in-place, modifies the input array)
// Time: O(n! * n), Space: O(n) recursion depth
const permute = (nums) => {
  const result = [];
 
  const backtrack = (start) => {
    if (start === nums.length) {
      result.push([...nums]);
      return;
    }
 
    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]]; // Swap in
      backtrack(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]]; // Swap back
    }
  };
 
  backtrack(0);
  return result;
};

The swap version is elegant but harder to adapt when you need to handle duplicates (Permutations II, LeetCode 47). The used[] version extends more cleanly — you just add a duplicate-skip condition.

Combinations (LeetCode 77)

Given integers n and k, return all combinations of k numbers chosen from 1 to n.

Combinations are subsets with an exact size constraint: only record a path when it reaches length k. Like subsets, order doesn't matter — [1, 2] and [2, 1] are the same combination.

// Backtracking with pruning
// Time: O(k * C(n, k)) — C(n, k) combinations, copying each costs O(k)
// Space: O(k) recursion depth
const combine = (n, k) => {
  const result = [];
 
  const backtrack = (start, current) => {
    if (current.length === k) {
      result.push([...current]);
      return;
    }
 
    // Pruning: we need (k - current.length) more numbers
    // If we start at i, we can get at most (n - i + 1) numbers
    // So we need: n - i + 1 >= k - current.length
    // Rearranged: i <= n - (k - current.length) + 1
    const remaining = k - current.length;
    for (let i = start; i <= n - remaining + 1; i++) {
      current.push(i);
      backtrack(i + 1, current);
      current.pop();
    }
  };
 
  backtrack(1, []);
  return result;
};

The upper bound n - remaining + 1 is the important pruning step. Without it, the code is still correct but slower. With n = 5, k = 3, and current = [1], you need 2 more numbers. Starting from index 4, you only have [4, 5] — exactly 2 numbers available, so 4 is the last valid starting point. Starting from 5 would leave only one option, making it impossible to complete a combination of size 3.

Counting recursive calls for n = 10, k = 5: the unpruned loop makes 638, the pruned one 462 — 176 calls that could only ever dead-end. Both return the same 252 combinations. The gap widens with n: at n = 20, k = 10 it is 616,666 calls versus 352,716.

The Three Problems Side by Side

Here's how the templates compare:

// SUBSETS — add at every node, use start to avoid reordering
const backtrackSubsets = (start, current) => {
  result.push([...current]);           // Every node
  for (let i = start; i < n; i++) {
    current.push(nums[i]);
    backtrackSubsets(i + 1, current);  // i + 1: no reuse
    current.pop();
  }
};
 
// PERMUTATIONS — add at leaves, use used[] to track available elements
const backtrackPerms = (current) => {
  if (current.length === n) { result.push([...current]); return; } // Leaf
  for (let i = 0; i < n; i++) {
    if (used[i]) continue;
    used[i] = true;
    current.push(nums[i]);
    backtrackPerms(current);           // No start: all unused elements available
    current.pop();
    used[i] = false;
  }
};
 
// COMBINATIONS — add at leaves (size == k), use start + pruning
const backtrackCombine = (start, current) => {
  if (current.length === k) { result.push([...current]); return; } // Leaf
  const remaining = k - current.length;
  for (let i = start; i <= n - remaining + 1; i++) { // Pruned upper bound
    current.push(i);
    backtrackCombine(i + 1, current);
    current.pop();
  }
};

The structural difference is:

• Where you add to results: every node (subsets) vs. only at leaves (permutations, combinations)
• What controls exploration: start index (subsets, combinations) vs. used[] array (permutations)

Interview Tips

Draw the decision tree first. Before writing a single line of code, sketch the tree for a small input (n = 3 or nums = [1, 2, 3]). Label which nodes get added to results, and what the recursion looks like at each level. This takes 30 seconds and eliminates most bugs.

Ask these three questions up front:

1. Does order matter? → Yes: permutations template. No: subsets/combinations template.
2. Can elements be reused? → No: i + 1 or used[]. Yes: pass i instead of i + 1.
3. What's the stop condition? → Size constraint (combinations), sum constraint (combination sum), or none (subsets).

The [...current] rule is non-negotiable. Write a comment next to it: // snapshot, not reference. If your interviewer asks why, explain that arrays are reference types — without spreading, you're storing a pointer to the same mutable array, which ends up empty after backtracking.

Know the complexities. Subsets: O(n * 2^n). Permutations: O(n * n!). Combinations: O(k * C(n, k)). If asked "can we do better?", the answer is almost always no — you have to generate all outputs, so you can't beat the size of the output set.

Variants to expect: Subsets II (input has duplicates — sort + skip on i > start && nums[i] === nums[i-1]), Permutations II (same skip trick with used[]), Letter Combinations of a Phone Number (backtracking over a string map). Same skeleton, minor adjustments.