/Projects
Coding patterns · 12 of 15

Backtracking

Choose, explore, un-choose.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot backtracking from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

Exponential: O(2ⁿ) subsets, O(n!) permutations Watch as reels
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

subsets.tsTypeScript
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
  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

combination-sum.tsTypeScript
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

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.tsTypeScript
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.tsTypeScript
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
AI Engineer · Backtracking