Backtracking pattern

Choose, explore, un-choose.

Part 1 of 5

Basics

The idea behind the pattern, why it is correct, and the clues in a question that point to it.

1.1Core idea

What the pattern does, in plain words.

Build a candidate one choice at a time. Recurse, then undo the choice so the next branch starts clean. Prune branches that cannot succeed as early as possible.

Why it works

Backtracking builds a solution one choice at a time, explores everything that choice allows, then undoes it and tries the next choice. It is a depth-first walk of the decision tree; pruning cuts off branches that cannot lead to a valid answer.

Typical cost: Exponential: O(2ⁿ) subsets, O(n!) permutations

1.2Recognition signals

If a question has one of these clues, try this pattern first.

All subsets, permutations or combinationsConstraint puzzles (N-Queens, Sudoku)Word search in a gridn is small (≤ 20)
Part 2 of 5

Question

A classic interview problem from this family. Read it carefully and plan the approach before writing any code.

2.1Combination Sum

The problem statement, then the plan you would say out loud.

Problem

Distinct candidates, reuse allowed. All combinations that sum to target.

Plan before you code

  1. Sort so you can stop early when a candidate is too big.
  2. Recurse with i (not i + 1) because reuse is allowed.
Part 3 of 5

Detailed answer

First the reusable template, then the worked solution built from it and a walk through it one step at a time.

3.1Template

Memorise this shape. Most problems in this family are this code plus one twist.

Subsets

TypeScriptKotlinJava
subsets.tsTypeScriptCopy
1function subsets(nums: number[]): number[][] {2  const out: number[][] = [], path: number[] = [];3  const go = (start: number): void => {4    out.push([...path]);   // copy!5    for (let i = start; i < nums.length; i++) {6      path.push(nums[i]);  // choose7      go(i + 1);           // explore8      path.pop();          // un-choose9    }10  };11  go(0);12  return out;13}
13 linesUTF-8TypeScript
subsets.ktKotlinCopy
1fun subsets(nums: IntArray): List<List<Int>> {2    val out = mutableListOf<List<Int>>()3    val path = mutableListOf<Int>()4    fun go(start: Int) {5        out.add(path.toList())   // copy!6        for (i in start until nums.size) {7            path.add(nums[i])                 // choose8            go(i + 1)                         // explore9            path.removeAt(path.lastIndex)     // un-choose10        }11    }12    go(0)13    return out14}
14 linesUTF-8Kotlin
subsets.javaJavaCopy
1static List<List<Integer>> subsets(int[] nums) {2  List<List<Integer>> out = new ArrayList<>();3  go(nums, 0, new ArrayList<>(), out);4  return out;5}6 7static void go(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {8  out.add(new ArrayList<>(path));   // copy!9  for (int i = start; i < nums.length; i++) {10    path.add(nums[i]);                    // choose11    go(nums, i + 1, path, out);           // explore12    path.remove(path.size() - 1);         // un-choose13  }14}
14 linesUTF-8Java
  1. Every node of the recursion tree is a subset; store a copy.
  2. Choose an element and recurse on the rest.
  3. Undo the choice so the next branch is clean.

3.2Solution

Strict TypeScript, type-checked and tested.

Combination Sum

TypeScriptKotlinJava
combination-sum.tsTypeScriptCopy
1function combinationSum(cands: number[], target: number): number[][] {2  cands.sort((a, b) => a - b);3  const out: number[][] = [], path: number[] = [];4  const go = (start: number, remain: number): void => {5    if (remain === 0) {6      out.push([...path]);7      return;8    }9    for (let i = start; i < cands.length; i++) {10      if (cands[i] > remain) break;   // prune: sorted11      path.push(cands[i]);12      go(i, remain - cands[i]);       // reuse allowed13      path.pop();14    }15  };16  go(0, target);17  return out;18}
18 linesUTF-8TypeScript
combination-sum.ktKotlinCopy
1fun combinationSum(cands: IntArray, target: Int): List<List<Int>> {2    cands.sort()3    val out = mutableListOf<List<Int>>()4    val path = mutableListOf<Int>()5    fun go(start: Int, remain: Int) {6        if (remain == 0) {7            out.add(path.toList())8            return9        }10        for (i in start until cands.size) {11            if (cands[i] > remain) break   // prune: sorted12            path.add(cands[i])13            go(i, remain - cands[i])       // reuse allowed14            path.removeAt(path.lastIndex)15        }16    }17    go(0, target)18    return out19}
19 linesUTF-8Kotlin
combination-sum.javaJavaCopy
1static List<List<Integer>> combinationSum(int[] cands, int target) {2  Arrays.sort(cands);3  List<List<Integer>> out = new ArrayList<>();4  combos(cands, 0, target, new ArrayList<>(), out);5  return out;6}7 8static void combos(int[] cands, int start, int remain, List<Integer> path, List<List<Integer>> out) {9  if (remain == 0) {10    out.add(new ArrayList<>(path));11    return;12  }13  for (int i = start; i < cands.length; i++) {14    if (cands[i] > remain) break;   // prune: sorted15    path.add(cands[i]);16    combos(cands, i, remain - cands[i], path, out);   // reuse allowed17    path.remove(path.size() - 1);18  }19}
19 linesUTF-8Java

Step by step

  1. Sort so we can stop early.
  2. Hit the target exactly: save a copy of the path.
  3. Prune: every later candidate is too big too.
  4. Choose, recurse with reuse allowed, un-choose.

Complexity: Exponential in target / min(candidate)

Part 4 of 5

Q&A

What interviewers ask once your code works, and problems to try on your own.

4.1Interview questions

Answer out loud, then open.

Why copy the path before saving it?
path is one array that keeps changing. Saving it directly stores a reference that ends up empty when the recursion unwinds.
How do you avoid duplicate combinations?
Sort, pass a start index so each element is only chosen after earlier ones, and skip equal neighbours at the same depth.
What is the complexity?
Exponential: 2ⁿ subsets, n! permutations. Say so, then explain how pruning helps in practice.

4.2Solo practice

Try these without looking; open the hint only when stuck.

MediumWord Search
Hint

DFS from each cell; mark visited, unmark on return.

Part 5 of 5

Extra depth

More fully worked problems in the same family, and the mistakes that cost offers.

5.12 more worked problems

Each one: the problem, the plan, the code and its cost.

Show detailsHide details
Medium

Permutations

Return every ordering of distinct numbers.

  1. Build the permutation one position at a time.
  2. Track which numbers are used.
  3. Undo the choice after exploring.
permutations.tsTypeScriptCopy
1function permute(nums: number[]): number[][] {2  const out: number[][] = [], path: number[] = [];3  const used = new Array<boolean>(nums.length).fill(false);4  const go = (): void => {5    if (path.length === nums.length) {6      out.push([...path]);7      return;8    }9    for (let i = 0; i < nums.length; i++) {10      if (used[i]) continue;11      used[i] = true;12      path.push(nums[i]);13      go();14      path.pop();15      used[i] = false;16    }17  };18  go();19  return out;20}
20 linesUTF-8TypeScript

Complexity: O(n · n!) time

Hard

N-Queens

Place n queens so none attack each other. Return every board.

  1. Place one queen per row.
  2. Columns and both diagonals (r − c, r + c) go in sets for O(1) checks.
  3. Undo all three on the way back.
nqueens.tsTypeScriptCopy
1function solveNQueens(n: number): string[][] {2  const out: string[][] = [], cols: number[] = [];3  const usedCols = new Set<number>(), diag = new Set<number>(), anti = new Set<number>();4  const go = (r: number): void => {5    if (r === n) {6      out.push(cols.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)));7      return;8    }9    for (let c = 0; c < n; c++) {10      if (usedCols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;11      cols.push(c);12      usedCols.add(c); diag.add(r - c); anti.add(r + c);13      go(r + 1);14      cols.pop();15      usedCols.delete(c); diag.delete(r - c); anti.delete(r + c);16    }17  };18  go(0);19  return out;20}
20 linesUTF-8TypeScript

Complexity: O(n!) time in the worst case

5.2Traps

Bugs and misreadings that come up again and again with this pattern.

Show detailsHide details
  • Appending path instead of path[:]
  • Forgetting to undo state
  • No pruning, so it times out