Backtracking

The shape: choose, explore, un-choose

Backtracking is DFS applied to a tree you build as you go — a decision tree, where each level represents one choice and each root-to-leaf path is one complete candidate answer. The "backtrack" part is the un-choose step: after exploring everything a choice leads to, you undo it before trying the next option, so the next branch starts from a clean slate.

The template every backtracking problem is built from

function backtrack(path, choices) {
  if (/* path is a complete valid answer */ false) {
    results.push([...path]); // COPY — path keeps mutating after this
    return;
  }

  for (const choice of choices) {
    if (/* choice is invalid right now */ false) continue; // pruning

    path.push(choice);          // 1. choose
    backtrack(path, nextChoices); // 2. explore
    path.pop();                  // 3. un-choose — THE step people forget
  }
}

Subsets — include or exclude, every element

function subsets(nums) {
  const results = [];
  function backtrack(start, path) {
    results.push([...path]); // every path is valid — push at every node, not just leaves
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path); // i + 1, not start + 1 — never reuse an earlier index
      path.pop();
    }
  }
  backtrack(0, []);
  return results;
}

Dry run: subsets([1, 2]) — the same tree as the figure above

Between the third and fourth rows, path.pop() runs twice on the way back out of the recursion — once undoing the 2, once undoing the 1 — before backtrack(2, [2]) ever starts. That's the un-choose step doing its job: [2] starts from a clean empty path, not from [1] left over from the branch before it.

Permutations — order matters, every element used exactly once

function permute(nums) {
  const results = [];
  function backtrack(path, used) {
    if (path.length === nums.length) {
      results.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // pruning: skip anything already placed
      used[i] = true;
      path.push(nums[i]);
      backtrack(path, used);
      path.pop();
      used[i] = false; // un-choose
    }
  }
  backtrack([], new Array(nums.length).fill(false));
  return results;
}

Combinations — like subsets, but with a fixed size

function combine(n, k) {
  const results = [];
  function backtrack(start, path) {
    if (path.length === k) {
      results.push([...path]);
      return;
    }
    // prune: if not enough numbers remain to reach size k, stop early
    for (let i = start; i <= n - (k - path.length) + 1; i++) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(1, []);
  return results;
}

That early-exit condition is real pruning, not just a style choice — it cuts off branches that provably can't reach a valid answer before ever recursing into them, which is where backtracking gets its practical speed despite the worst-case complexity being exponential.

Why the complexity looks scary and that's expected

This isn't a bug to optimize away — it's inherent to "generate every valid X." What you can optimize is how much of the tree you actually visit, by pruning invalid branches as early as possible (as seen in the N-Queens example below) rather than generating a full candidate and checking it after the fact.

N-Queens — pruning is what makes it tractable

function solveNQueens(n) {
  const results = [];
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  const placement = [];

  function backtrack(row) {
    if (row === n) {
      results.push([...placement]);
      return;
    }
    for (let col = 0; col < n; col++) {
      const d1 = row - col, d2 = row + col;
      if (cols.has(col) || diag1.has(d1) || diag2.has(d2)) continue; // prune — this column/diagonal is under attack

      cols.add(col); diag1.add(d1); diag2.add(d2);
      placement.push(col);

      backtrack(row + 1);

      cols.delete(col); diag1.delete(d1); diag2.delete(d2); // backtrack
      placement.pop();
    }
  }
  backtrack(0);
  return results;
}

Word Search — backtracking over a grid instead of an array

The same choose/explore/un-choose shape, just with "neighbors in a grid" as the branching factor instead of "remaining array elements." This combines directly with the grid-traversal ideas from the matrix chapter.

function exist(board, word) {
  const rows = board.length, cols = board[0].length;

  function backtrack(r, c, i) {
    if (i === word.length) return true; // matched every character — done
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[i]) return false;

    const temp = board[r][c];
    board[r][c] = "#"; // mark visited IN PLACE — avoids a separate visited set

    const found =
      backtrack(r + 1, c, i + 1) ||
      backtrack(r - 1, c, i + 1) ||
      backtrack(r, c + 1, i + 1) ||
      backtrack(r, c - 1, i + 1);

    board[r][c] = temp; // UN-CHOOSE — restore before trying a different path
    return found;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (backtrack(r, c, 0)) return true;
    }
  }
  return false;
}

Combination Sum — when you're allowed to reuse an element

Unlike combine() earlier, the same number can be picked more than once. The fix is a one-character change with a real consequence: recurse with i, not i + 1.

function combinationSum(candidates, target) {
  const results = [];
  function backtrack(start, path, remaining) {
    if (remaining === 0) { results.push([...path]); return; }
    if (remaining < 0) return; // prune — overshot, no point continuing

    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      backtrack(i, path, remaining - candidates[i]); // i, not i+1 — this number can be reused
      path.pop();
    }
  }
  backtrack(0, [], target);
  return results;
}

This single index difference (i vs i + 1) is worth internalizing as its own decision point: "can this choice repeat?" is usually the very first question to answer before writing the loop — it changes one character, but changes the whole shape of the search space.

Duplicates in the input — sort, then skip at the same level

Everything so far assumed the input values are distinct. Once they are not, the tree itself still has the right shape, but different branches produce the same answer. Take [1, 2, 2] and the plain subsets code: choosing the first 2 and then nothing gives [1, 2], and choosing the second 2 and then nothing gives [1, 2] again. The plain code returns [[], [1], [1, 2], [1, 2, 2], [1, 2], [2], [2, 2], [2]]: eight lists, but only six different ones.

The fix comes from asking where the two copies of [1, 2] diverge. Both start from [1], and then in the same loop one branch picks the 2 at index 1 and the other picks the 2 at index 2. Two siblings in the same loop holding equal values lead to the same answers: the earlier sibling's subtree can still reach everything that the later sibling's subtree can. So: in one loop, try each distinct value once. Sort the input so equal values sit next to each other, and skip a value when it equals the one just before it in the same loop.

function subsetsWithDup(nums) {
  const sorted = [...nums].sort((a, b) => a - b); // equal values must sit next to each other
  const results = [];

  function backtrack(start, path) {
    results.push([...path]);
    for (let i = start; i < sorted.length; i++) {
      if (i > start && sorted[i] === sorted[i - 1]) continue; // same value already tried at THIS level
      path.push(sorted[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return results;
}

The condition is i > start, not i > 0, and that difference is the whole idea. i === start is the first value this loop tries, so there is nothing before it to repeat. A value that equals its neighbour is only a duplicate if that neighbour was tried in the same loop. Equal values at different depths are fine and necessary: the 2 in [1, 2, 2] is chosen at one level and the next 2 at the level below it, and that is how [1, 2, 2] gets built.

Dry run: subsetsWithDup([1, 2, 2])

Two skips, and exactly the two repeated lists disappear. The result has six entries. Time is O(n · 2ⁿ) at worst: up to 2ⁿ subsets, each costing O(n) to copy.

Permutations with repeated values

The same sentence works for permutations, with one wrinkle: permutations loop over all positions each time, using a used array, so "the previous value in the same loop" must also be unused to count as a sibling. The rule is: skip index i if it equals sorted[i - 1] and sorted[i - 1] is not currently used. Intuitively, equal values are interchangeable, so you insist they enter the path in their original left-to-right order; a twin may only be placed when the twin before it is already in the path.

function permuteUnique(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  const results = [];
  const used = new Array(sorted.length).fill(false);
  const path = [];

  function backtrack() {
    if (path.length === sorted.length) {
      results.push([...path]);
      return;
    }
    for (let i = 0; i < sorted.length; i++) {
      if (used[i]) continue;
      if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) continue; // equal twins are used left to right
      used[i] = true;
      path.push(sorted[i]);
      backtrack();
      path.pop();
      used[i] = false;
    }
  }

  backtrack();
  return results;
}

For [1, 1, 2] there are 3 distinct permutations, against 3! = 6 in the plain code. Step by step: the root tries i = 0 (a 1), and inside it both the second 1 (allowed, since the first is used) and the 2 are tried, giving [1, 1, 2] and [1, 2, 1]. Back at the root, i = 1 is a 1 whose twin at index 0 is unused, so it is skipped. Then i = 2 starts [2, ...] and inside it index 0 is taken, index 1 is skipped for the same reason, giving [2, 1, 1].

There is a second way that avoids the index rule entirely: count the values, and let each level branch once per distinct value that still has a count left. Equal values can never be chosen as two separate siblings because they are one entry in the map.

function permuteUniqueCounts(nums) {
  const counts = new Map();
  for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
  const results = [];
  const path = [];

  function backtrack() {
    if (path.length === nums.length) {
      results.push([...path]);
      return;
    }
    for (const [value, left] of counts) { // one branch per DISTINCT value
      if (left === 0) continue;
      counts.set(value, left - 1);
      path.push(value);
      backtrack();
      path.pop();
      counts.set(value, left);
    }
  }

  backtrack();
  return results;
}

Combination Sum II — each element once, duplicates in the input

Candidates may repeat ([10, 1, 2, 7, 6, 1, 5]), and each position may be used at most once, so the recursive call is i + 1 as in subsets. The same-level skip removes duplicate answers. Sorting also buys a second, separate saving: once sorted[i] is larger than what remains, every later value in the loop is too, so break ends the loop instead of continuing it.

function combinationSum2(candidates, target) {
  const sorted = [...candidates].sort((a, b) => a - b);
  const results = [];

  function backtrack(start, path, remaining) {
    if (remaining === 0) {
      results.push([...path]);
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      if (sorted[i] > remaining) break; // sorted: every later value is too big as well
      if (i > start && sorted[i] === sorted[i - 1]) continue; // same value already tried at this level
      path.push(sorted[i]);
      backtrack(i + 1, path, remaining - sorted[i]); // i + 1: each element is used at most once
      path.pop();
    }
  }

  backtrack(0, [], target);
  return results;
}

With target 8 the answer is [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. Note that [1, 1, 6] is kept: its second 1 is chosen one level deeper than the first, where it is not a sibling. The same-level skip fires only once, at the top, when the loop reaches the second 1 after the first 1's whole subtree has been explored, which would otherwise have produced [1, 2, 5] and [1, 7] a second time.

Cut-point backtracking — splitting a string into valid pieces

So far each level chose which element comes next. A different family chooses where to cut a string. The state is a single number, start, the first character of the piece you have not placed yet; a level tries every possible end of the next piece; and a branch is only worth entering when the piece it cuts is acceptable. The pruning happens on the piece, before recursing.

Palindrome Partitioning asks for every way to split a string so that every piece is a palindrome. The loop is over the end of the next piece, the test is "is s[start..end] a palindrome", and the base case is reaching the end of the string.

function partition(s) {
  const n = s.length;
  const results = [];
  const pieces = [];

  function isPalindrome(lo, hi) {
    while (lo < hi) {
      if (s[lo++] !== s[hi--]) return false;
    }
    return true;
  }

  function backtrack(start) {
    if (start === n) {
      results.push([...pieces]);
      return;
    }
    for (let end = start; end < n; end++) { // the piece is s[start..end]: choose where to cut
      if (!isPalindrome(start, end)) continue;
      pieces.push(s.slice(start, end + 1));
      backtrack(end + 1); // the next piece starts right after the cut
      pieces.pop();
    }
  }

  backtrack(0);
  return results;
}

Dry run: partition("aab")

The cost has a different shape from subsets. On "aaaa…a" of length n every cut is allowed, so there are 2ⁿ⁻¹ partitions (1, 2, 4, 8 for lengths 1 to 4), and each costs O(n) to copy and to test. The palindrome test alone adds a factor of n per piece. To pay for it once, precompute a table isPal[lo][hi] in O(n²), after which each test is O(1):

function buildPalindromeTable(s) {
  const n = s.length;
  const isPal = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let lo = n - 1; lo >= 0; lo--) { // lo goes right to left so isPal[lo + 1][hi - 1] is ready
    for (let hi = lo; hi < n; hi++) {
      isPal[lo][hi] = s[lo] === s[hi] && (hi - lo < 2 || isPal[lo + 1][hi - 1]);
    }
  }
  return isPal;
}

A substring is a palindrome when its two end characters match and the part between them is a palindrome (or has fewer than two characters). The loop over lo runs from the right end so that isPal[lo + 1][hi - 1] already exists. This is a small 2D dynamic programming table. The backtracking itself is unchanged, with isPal[start][end] in place of the helper.

Restore IP Addresses is the same skeleton with exactly four pieces and validity rules built into the loop: each piece has one to three digits, no leading zero unless the piece is the single digit 0, and a value of at most 255. Because the number of pieces is fixed, a strong prune is available: at any point, the characters left must fit in the pieces left, at least one and at most three each.

function restoreIpAddresses(s) {
  const results = [];
  const parts = [];

  function backtrack(start) {
    const partsLeft = 4 - parts.length;
    const charsLeft = s.length - start;
    if (charsLeft < partsLeft || charsLeft > 3 * partsLeft) return; // cannot fit: prune early
    if (partsLeft === 0) {
      results.push(parts.join("."));
      return;
    }
    for (let len = 1; len <= 3; len++) {
      const piece = s.slice(start, start + len);
      if (piece.length < len) break; // ran off the end of the string
      if (piece.length > 1 && piece[0] === "0") break; // no leading zeros: "0" is fine, "01" is not
      if (Number(piece) > 255) break;
      parts.push(piece);
      backtrack(start + len);
      parts.pop();
    }
  }

  backtrack(0);
  return results;
}

For "25525511135" the two answers are 255.255.11.135 and 255.255.111.35. The search is tiny: at most 3 choices at each of 4 levels, so at most 81 leaves, which makes the running time O(1) for a fixed address length of 4 pieces. The length check is what lets a string like "1111111111111" (13 digits) return immediately instead of searching.

Letter Combinations — one decision per position

Given a string of digits, return every letter string a phone keypad could spell. Here the levels are the positions of the input, and the loop at each level runs over the letters of that position's digit. Nothing needs a start index, because every position is decided exactly once and in order, and no choice depends on an earlier one.

function letterCombinations(digits) {
  if (digits.length === 0) return []; // not [""]: no digits means no combinations
  const letters = { 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz" };
  const results = [];
  const path = [];

  function backtrack(position) {
    if (position === digits.length) {
      results.push(path.join(""));
      return;
    }
    for (const ch of letters[digits[position]]) { // one decision per digit position
      path.push(ch);
      backtrack(position + 1);
      path.pop();
    }
  }

  backtrack(0);
  return results;
}

For "23" the answer is the nine strings ad, ae, af, bd, be, bf, cd, ce, cf. The number of leaves is the product of the letter counts, at most 4ⁿ because digits 7 and 9 have four letters, and each result costs O(n) to join, so the time is O(4ⁿ · n).

Generate Parentheses — prune on counts, not at the leaf

Produce every string of n pairs of parentheses that is well formed: reading left to right, you never close more than you have opened, and at the end the counts match. Generating all 2²ⁿ strings and testing each one is correct but wasteful: for n = 8 that is 65,536 strings against 1,430 valid ones.

Build the string one character at a time and track two numbers, open and close. The two rules translate directly into the two branches. You may add ( while open < n. You may add ) only while close < open, since otherwise there is nothing to close. Every string the recursion finishes is well formed by construction, so there is no validity check at the leaves.

function generateParenthesis(n) {
  const results = [];
  const path = [];

  function backtrack(open, close) {
    if (path.length === 2 * n) {
      results.push(path.join(""));
      return;
    }
    if (open < n) { // we may open while we still have openers left
      path.push("(");
      backtrack(open + 1, close);
      path.pop();
    }
    if (close < open) { // we may close only what is already open
      path.push(")");
      backtrack(open, close + 1);
      path.pop();
    }
  }

  backtrack(0, 0);
  return results;
}

Dry run: generateParenthesis(2)

The results are ["(())", "()()"]. For n = 3 the function returns ["((()))", "(()())", "(())()", "()(())", "()()()"]. The counts of valid strings for n = 1, 2, 3, ... are 1, 2, 5, 14, 42, 132, ... (the Catalan numbers). The recursion makes 22 calls for n = 3 and 6,917 for n = 8.

Complexity follows from one observation: this tree has no dead ends. Whenever the path is shorter than 2n, at least one branch is open: if open < n, add (; otherwise open = n and close < n = open, so add ). Every node therefore has a result below it, so the number of nodes is at most the number of results times the depth. Time is O(n · Cₙ), where Cₙ is the n-th Catalan number, which grows roughly like 4ⁿ up to a polynomial factor. The recursion depth and the extra space are O(n).

Per-position or per-element? A decision table

Every problem in this chapter has the same template; what changes is what a level decides and what the loop ranges over. Settling those two things before writing code is the real work. Almost every bug in this chapter is one of them answered wrongly.

Two questions pick almost every cell of that table. Is order part of the answer? If [1, 2] and [2, 1] are different answers (permutations), every level looks at everything unused and there is no start. If they are the same answer (subsets, combinations), the loop starts at start so each set is built in one order only. Can an element be reused? Reuse recurses with i, no reuse with i + 1.

The cost of a backtracking solution is always (number of leaves, or results) × (work per result). The work per result is the copy, usually O(n), plus any test you run at the node, such as the palindrome check. That is why subsets are O(n · 2ⁿ), permutations O(n · n!), and why the output itself often sets the floor: if the answer has a million lists, no pruning can make the program faster than writing them. Pruning improves how much of the tree you visit, not what an answer costs.

Recognizing it in an unseen problem

• "All possible," "every combination," "every way to," "generate all"
• A brute force would need to try every candidate and check validity after the fact — backtracking checks validity during construction and prunes early
• The answer is built incrementally (one element/choice at a time), and a partial answer can be judged "still possibly valid" or "already invalid"
• Grid-based "does a path exist" → Word Search shape; mark-and-restore in place instead of a separate visited set
• "Elements can be reused" → recurse with the same index, not the next one
• The input has repeated values but the answer must not repeat → sort, and skip a value equal to the previous one in the same loop (i > start)
• A string must be split into valid pieces → cut-point backtracking: the state is start, the loop ranges over where the next piece ends, and the piece is tested before recursing
• A rule that can be judged on a prefix (counts, a numeric range, no leading zero) → put it in the loop condition so the branch is never entered, not in a check at the leaf
• If it instead asks for the best single answer rather than all answers, check whether greedy or DP applies first — those are usually faster than exploring the whole tree