GUIDE · Recursion
Backtracking
DFS over a decision tree; build a partial solution, recurse, undo. Enumerate or search.
At a glance
- WHAT
- DFS over a decision tree; build a partial solution, recurse, undo. Enumerate or search.
- TELL
- "all possible", "generate all", "combinations / permutations / subsets", "place N ...", "valid arrangements", "partition into", constraints small (n <= ~20).
- SAY
- choose / explore / un-choosedecision treepruningstate spacestart index (combinations) vs used[] (permutations)skip duplicates after sortingconstraint propagation
- BIG-O
- subsets O(2^n * n); permutations O(n! * n); combinations O(C(n,k) * k). Output-sensitive.
The idea#
Picture a maze drawn on paper. You stand at the entrance with a pencil. You step into a corridor, draw a line behind you, and keep going. When you hit a wall, you walk back to the last corner and erase that last step. Then you try the next corridor. You are building a path, exploring it, and undoing the choice that failed.
That is backtracking. The maze is a decision tree. Each corner is a choice: include this number or skip it, place this queen or try the next column, add an open parenthesis or a close one. You push the choice onto a path, recurse, and when that call returns you pop the choice off. Choose, explore, un-choose. The partial path is the pencil line. The pop is the eraser.
The template is one function. If the path is a finished answer, copy it into the results and return. Copy, because the path array will be mutated on the way back out. Then for each legal choice, skip the ones that break a rule, mark the choice, recurse, and unmark it. Pruning is refusing a corridor you can already see is a dead end, before you walk it.
Combinations and subsets pass a start index, so order does not matter and you never reuse an earlier item. Permutations pass a used array, so every item is considered at every position. When the input has duplicates, sort first, then skip a value that matches the one you just skipped at this same level.
Why it matters#
You reach for this when the problem says "all possible," "generate all," combinations, permutations, subsets, "place N" of something, "valid arrangements," or "partition into." The constraint is small. Once n is past about twenty, the maze is too big to walk.
The cost follows the shape of the maze, and it is output-sensitive: you pay for every answer you write down. Subsets are O(2^n · n). Permutations are O(n! · n). Combinations of k out of n are O(C(n, k) · k).
A small example#
function subsets(nums) { const out = []; const path = []; function walk(start) { out.push(path.slice()); for (let i = start; i < nums.length; i++) { path.push(nums[i]); walk(i + 1); path.pop(); } } walk(0); return out;} const kits = subsets([1, 2]);kits holds [], [1], [1, 2], and [2]. path.slice() is the copy. path.pop() is the walk back to the last corner. The start index is why [2, 1] never appears.
What the code below is doing#
The sheet prints the template first: goal, prune, choose, explore, un-choose, plus the start-index rule, the used[] rule, and the sorted-duplicate skip. Subsets walk that template, include-or-not from a start index. Subsets II sorts and skips a[i] === a[i - 1] when i > start. Permutations swap in a used flag and stop when the path length equals n. Permutations II sorts and skips a duplicate whose previous twin is unused, so the same value is only taken in order.
Combinations C(n, k) keep a start index and prune when the remaining numbers are fewer than you still need. Combination sum allows reuse by recursing at the same index, and breaks early once a sorted candidate overshoots the target. Combination sum II uses each element once and skips equal siblings. Generate parentheses adds '(' while opens are under n, and ')' while closes are under opens. That count is the Catalan shape, on the order of 4^n over square root of n. Letter combinations of a phone number take one letter per digit, per level, O(4^n · n).
N-Queens places one queen per row and keeps sets of used columns, diagonals r - c, and anti-diagonals r + c. Word search is the maze on a grid: mark a cell, try four directions, restore the cell on the way out, O(mn · 3^L) for a word of length L. Palindrome partitioning cuts at every end index where the slice is a palindrome. Sudoku finds an empty cell, tries the digits that survive the row, column, and box, and undoes the digit when the recursive call fails.
When you talk about it, say this: choose, explore, un-choose, and copy the path when it is done.
Everything below is the demonstration. Same idea, written as code you can run.
'use strict';const assert = require('node:assert/strict');TEMPLATE#
// function backtrack(path, choices/state):// if GOAL(path): result.push([...path]); return // COPY the path// for each choice c in choices:// if NOT VALID(c): continue // prune// path.push(c); mark(c) // choose// backtrack(path, next state) // explore// path.pop(); unmark(c) // un-choose// Combinations/subsets: pass a START index so order does not matter (no repeats).// Permutations: pass a used[] array so every element is considered at every position.// Duplicates: SORT FIRST, then `if (i > start && a[i] === a[i-1]) continue` (or !used[i-1] for permutations).Subsets (power set)#
at each index, include or not; or start-index loop
function subsets(nums) { const out = [], path = []; const bt = (start) => { out.push([...path]); for (let i = start; i < nums.length; i++) { path.push(nums[i]); bt(i + 1); path.pop(); } }; bt(0); return out;}Verified by 2 asserts
assert.deepEqual(subsets([1, 2, 3]), [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]);assert.deepEqual(subsets([]), [[]]);Subsets II (with duplicates)#
sort; skip a[i] === a[i-1] when i > start
function subsetsWithDup(nums) { nums = [...nums].sort((a, b) => a - b); const out = [], path = []; const bt = (start) => { out.push([...path]); for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) continue; path.push(nums[i]); bt(i + 1); path.pop(); } }; bt(0); return out;}Verified by 2 asserts
assert.deepEqual(subsetsWithDup([1, 2, 2]), [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]);assert.deepEqual(subsetsWithDup([0]), [[], [0]]);Permutations#
used[] flags; goal when path.length === n
function permute(nums) { const out = [], path = [], used = new Array(nums.length).fill(false); const bt = () => { if (path.length === nums.length) { out.push([...path]); return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; used[i] = true; path.push(nums[i]); bt(); path.pop(); used[i] = false; } }; bt(); return out;}Verified by 2 asserts
assert.deepEqual(permute([1, 2, 3]), [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]);assert.deepEqual(permute([]), [[]]);Permutations II (with duplicates)#
sort; skip if a[i] === a[i-1] && !used[i-1]
function permuteUnique(nums) { nums = [...nums].sort((a, b) => a - b); const out = [], path = [], used = new Array(nums.length).fill(false); const bt = () => { if (path.length === nums.length) { out.push([...path]); return; } for (let i = 0; i < nums.length; i++) { if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) continue; // same value, earlier twin not used => dup branch used[i] = true; path.push(nums[i]); bt(); path.pop(); used[i] = false; } }; bt(); return out;}Verified by 2 asserts
assert.deepEqual(permuteUnique([1, 1, 2]), [[1, 1, 2], [1, 2, 1], [2, 1, 1]]);assert.deepEqual(permuteUnique([2, 2]), [[2, 2]]);Combinations C(n, k)#
start index; prune when remaining < needed
function combine(n, k) { const out = [], path = []; const bt = (start) => { if (path.length === k) { out.push([...path]); return; } for (let i = start; i <= n - (k - path.length) + 1; i++) { path.push(i); bt(i + 1); path.pop(); } // pruned upper bound }; bt(1); return out;}Verified by 2 asserts
assert.deepEqual(combine(4, 2), [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]);assert.deepEqual(combine(1, 1), [[1]]);Combination sum I (reuse allowed)#
recurse with same i; prune when remaining < 0 (sorted => break)
function combinationSum(cands, target) { cands = [...cands].sort((a, b) => a - b); const out = [], path = []; const bt = (start, remain) => { if (remain === 0) { out.push([...path]); return; } for (let i = start; i < cands.length; i++) { if (cands[i] > remain) break; // sorted: nothing further fits path.push(cands[i]); bt(i, remain - cands[i]); path.pop(); // i, not i+1 => reuse } }; bt(0, target); return out;}Verified by 2 asserts
assert.deepEqual(combinationSum([2, 3, 6, 7], 7), [[2, 2, 3], [7]]);assert.deepEqual(combinationSum([2], 1), []);Combination sum II (each once, duplicates in input)#
i+1 and skip equal siblings
function combinationSum2(cands, target) { cands = [...cands].sort((a, b) => a - b); const out = [], path = []; const bt = (start, remain) => { if (remain === 0) { out.push([...path]); return; } for (let i = start; i < cands.length; i++) { if (cands[i] > remain) break; if (i > start && cands[i] === cands[i - 1]) continue; path.push(cands[i]); bt(i + 1, remain - cands[i]); path.pop(); } }; bt(0, target); return out;}Verified by 2 asserts
assert.deepEqual(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8), [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]);assert.deepEqual(combinationSum2([2, 5, 2, 1, 2], 5), [[1, 2, 2], [5]]);Generate parentheses#
add '(' if open < n; add ')' if close < open
function generateParenthesis(n) { const out = []; const bt = (s, open, close) => { if (s.length === 2 * n) { out.push(s); return; } if (open < n) bt(s + '(', open + 1, close); if (close < open) bt(s + ')', open, close + 1); }; bt('', 0, 0); return out;}Verified by 2 asserts
assert.deepEqual(generateParenthesis(3), ['((()))', '(()())', '(())()', '()(())', '()()()']);assert.deepEqual(generateParenthesis(1), ['()']);Letter combinations of a phone number#
digit -> letters; one letter per level
function letterCombinations(digits) { if (!digits) return []; const map = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' }; const out = []; const bt = (i, s) => { if (i === digits.length) { out.push(s); return; } for (const ch of map[digits[i]]) bt(i + 1, s + ch); }; bt(0, ''); return out;}Verified by 2 asserts
assert.deepEqual(letterCombinations('23'), ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']);assert.deepEqual(letterCombinations(''), []);N-Queens#
one queen per row; sets for cols, diag (r-c), anti-diag (r+c)
function solveNQueens(n) { const boards = [], cols = new Set(), d1 = new Set(), d2 = new Set(), pos = []; const bt = (r) => { if (r === n) { boards.push(pos.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))); return; } for (let c = 0; c < n; c++) { if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue; cols.add(c); d1.add(r - c); d2.add(r + c); pos.push(c); bt(r + 1); cols.delete(c); d1.delete(r - c); d2.delete(r + c); pos.pop(); } }; bt(0); return boards;}Verified by 4 asserts
assert.equal(solveNQueens(4).length, 2);assert.deepEqual(solveNQueens(4)[0], ['.Q..', '...Q', 'Q...', '..Q.']);assert.equal(solveNQueens(8).length, 92);assert.equal(solveNQueens(3).length, 0);Word search (grid DFS with visited)#
mark cell '#', explore 4 dirs, restore
function exist(board, word) { const m = board.length, n = board[0].length; const dfs = (r, c, i) => { if (i === word.length) return true; if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] !== word[i]) return false; const ch = board[r][c]; board[r][c] = '#'; const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1); board[r][c] = ch; return found; }; for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (dfs(r, c, 0)) return true; return false;}const board = [['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']];Verified by 3 asserts
assert.equal(exist(board, 'ABCCED'), true);assert.equal(exist(board, 'ABCB'), false); // cannot reuse a cellassert.equal(exist([['a']], 'a'), true);Palindrome partitioning#
cut at every j where s[start..j] is a palindrome
function partition(s) { const out = [], path = []; const isPal = (i, j) => { while (i < j) if (s[i++] !== s[j--]) return false; return true; }; const bt = (start) => { if (start === s.length) { out.push([...path]); return; } for (let j = start; j < s.length; j++) if (isPal(start, j)) { path.push(s.slice(start, j + 1)); bt(j + 1); path.pop(); } }; bt(0); return out;}Verified by 2 asserts
assert.deepEqual(partition('aab'), [['a', 'a', 'b'], ['aa', 'b']]);assert.deepEqual(partition('a'), [['a']]);Sudoku solver sketch#
find empty cell; try 1-9 that pass row/col/box check; recurse; undo on failure
function solveSudoku(b) { const ok = (r, c, d) => { for (let i = 0; i < 9; i++) { if (b[r][i] === d || b[i][c] === d) return false; if (b[3 * ((r / 3) | 0) + ((i / 3) | 0)][3 * ((c / 3) | 0) + (i % 3)] === d) return false; } return true; }; const bt = () => { for (let r = 0; r < 9; r++) for (let c = 0; c < 9; c++) if (b[r][c] === '.') { for (let d = 1; d <= 9; d++) if (ok(r, c, String(d))) { b[r][c] = String(d); if (bt()) return true; b[r][c] = '.'; } return false; // no digit fits: backtrack } return true; // no empty cell left }; bt(); return b;}const sudoku = ['53..7....', '6..195...', '.98....6.', '8...6...3', '4..8.3..1', '7...2...6', '.6....28.', '...419..5', '....8..79'].map((r) => r.split(''));const solved = solveSudoku(sudoku);Verified by 3 asserts
assert.equal(solved[0].join(''), '534678912');assert.equal(solved[8].join(''), '345286179');assert.ok(solved.every((row) => new Set(row).size === 9));See also