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.
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.
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.
Distinct candidates, reuse allowed. All combinations that sum to target.
Plan before you code
- Sort so you can stop early when a candidate is too big.
- Recurse with i (not i + 1) because reuse is allowed.
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
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}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}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}- Every node of the recursion tree is a subset; store a copy.
- Choose an element and recurse on the rest.
- Undo the choice so the next branch is clean.
3.2Solution
Strict TypeScript, type-checked and tested.
Combination Sum
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}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}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}Step by step
- Sort so we can stop early.
- Hit the target exactly: save a copy of the path.
- Prune: every later candidate is too big too.
- Choose, recurse with reuse allowed, un-choose.
Complexity: Exponential in target / min(candidate)
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?
How do you avoid duplicate combinations?
What is the complexity?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
DFS from each cell; mark visited, unmark on return.
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
Permutations
Return every ordering of distinct numbers.
- Build the permutation one position at a time.
- Track which numbers are used.
- Undo the choice after exploring.
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}Complexity: O(n · n!) time
N-Queens
Place n queens so none attack each other. Return every board.
- Place one queen per row.
- Columns and both diagonals (r − c, r + c) go in sets for O(1) checks.
- Undo all three on the way back.
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}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