13 — Backtracking

What backtracking is

Backtracking is DFS over a tree of decisions. At each step you make a choice, explore everything that follows from it, then undo the choice and try the next one.

"Undo" is the whole idea. You're reusing one mutable piece of state (a list, a board) across millions of branches, so after exploring a branch you must restore the state exactly as you found it.

Seeing the decision tree

For subsets of [1, 2], each element is either in or out:

                    []
              /            \
         include 1      exclude 1
            [1]              []
          /     \          /     \
     incl 2   excl 2   incl 2   excl 2
      [1,2]    [1]      [2]      []

Four leaves = four subsets. Backtracking walks this tree depth-first.

When to reach for it

The tells are unmistakable:

• "Return all ..." — the output is an enumeration.
• "How many distinct ways ..." when you must actually list them.
• n ≤ 20 with no polynomial algorithm in sight.

Small constraints are the interviewer telling you exponential is expected. Stop hunting for something clever and write the backtracking.

The universal skeleton

private void backtrack(State state, List<Result> results) {
    if (isComplete(state)) {
        results.add(copyOf(state));      // COPY — the live state keeps mutating
        return;
    }
    for (Choice c : choicesFrom(state)) {
        if (!isValid(c, state)) continue;   // PRUNE

        apply(c, state);                    // CHOOSE
        backtrack(state, results);          // EXPLORE
        undo(c, state);                     // UN-CHOOSE
    }
}

Four questions define any backtracking problem. Answer them out loud before writing code:

1. What is the state? (a path, an index, a partial board)
2. When is it complete? (the base case)
3. What are the choices at each step? (the loop)
4. What makes a choice invalid? (the prune)

The number-one bug: forgetting to copy

results.add(path);                    // WRONG — stores a REFERENCE
results.add(new ArrayList<>(path));   // correct — stores a SNAPSHOT

path is one list you keep mutating. Storing a reference means every result points at the same object — and by the end that object is empty. You get [[], [], [], []].

The copy is O(n) per result, which is why backtracking complexities usually carry a factor of n.

Family 1 — subsets (include / exclude)

Each element is independently in or out: 2^n subsets.

The explicit two-branch form

List<List<Integer>> res = new ArrayList<>();

private void backtrack(int i, int[] nums, List<Integer> path) {
    if (i == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    path.add(nums[i]);              // branch 1: INCLUDE nums[i]
    backtrack(i + 1, nums, path);
    path.remove(path.size() - 1);   // UN-CHOOSE

    backtrack(i + 1, nums, path);   // branch 2: EXCLUDE nums[i]
}

This mirrors the decision tree directly. Note the un-choose sits between the two branches — the exclude branch must start from a clean path.

The loop form — prefer this once comfortable

private void backtrack(int start, int[] nums, List<Integer> path) {
    res.add(new ArrayList<>(path));            // EVERY node is a valid subset

    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(i + 1, nums, path);          // i + 1: never reuse, never look back
        path.remove(path.size() - 1);
    }
}

Two differences worth understanding:

1. res.add happens at every node, not just at leaves. Every partial path is itself a valid subset — [], [1], [1,2] are all answers.

2. start is what prevents duplicates. By only looking forward from start, you generate [1,2] but never [2,1]. For subsets, order doesn't matter, so generating both would be wrong.

This form generalizes to combinations, which is why it's worth adopting.

Family 2 — combinations with a target

Combination Sum — unlimited reuse

Find all combinations of candidates summing to target; each number may be used any number of times.

private void backtrack(int start, int[] candidates, int remaining, List<Integer> path) {
    if (remaining == 0) { res.add(new ArrayList<>(path)); return; }   // exact hit
    if (remaining < 0) return;                                        // overshot — PRUNE

    for (int i = start; i < candidates.length; i++) {
        path.add(candidates[i]);
        backtrack(i, candidates, remaining - candidates[i], path);    // i, NOT i+1
        path.remove(path.size() - 1);
    }
}

backtrack(i, ...) is what allows reuse. Passing i (not i + 1) means the same element can be chosen again at the next level. Passing i + 1 would forbid reuse.

Trace: candidates = [2, 3, 6, 7], target = 7.

[]  rem=7
├─ 2  rem=5
│  ├─ 2  rem=3
│  │  ├─ 2  rem=1
│  │  │  └─ 2 → rem=-1 ✗ prune
│  │  └─ 3  rem=0 ✓  →  [2,2,3]
│  ├─ 3  rem=2 → 3 gives rem=-1 ✗
│  └─ 6, 7 → negative ✗
├─ 3  rem=4 → 3 gives rem=1 → nothing works
├─ 6  rem=1 ✗
└─ 7  rem=0 ✓  →  [7]

Result: [[2,2,3], [7]]. ✓

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

Two changes from the above:

Arrays.sort(candidates);                             // REQUIRED for the dedup

private void backtrack(int start, int[] candidates, int remaining, List<Integer> path) {
    if (remaining == 0) { res.add(new ArrayList<>(path)); return; }
    if (remaining < 0) return;

    for (int i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) continue;   // DEDUP
        path.add(candidates[i]);
        backtrack(i + 1, candidates, remaining - candidates[i], path);   // i+1 — no reuse
        path.remove(path.size() - 1);
    }
}

The dedup rule — the most important detail in this section

if (i > start && candidates[i] == candidates[i - 1]) continue;

What it means

Read it as: "at this level of the tree, a given value may start a branch only once."

If you have [1, 1, 2] and you're choosing the first element, picking the first 1 and picking the second 1 lead to identical subtrees. Exploring both produces duplicate results.

Why i > start and NOT i > 0

This is the detail that gets fumbled. Consider candidates = [1, 1, 6], target = 8. The valid answer is [1, 1, 6] — using both ones.

With i > 0 instead, the level-2 case (i = 1) would also be skipped — and you'd lose the valid answer [1, 1, 6].

i > start means "this isn't the first choice at this level." Deeper levels have a larger start, so legitimate reuse of an equal value at a deeper level is unaffected.

Why sorting is required

Sorting makes equal values adjacent, so "is this a duplicate of the previous choice?" is a single O(1) comparison with candidates[i-1]. Unsorted, you'd need a Set of seen values per level.

The same rule, verbatim, applies to Subsets II.

Family 3 — permutations

Order matters, so every remaining element is a candidate at every position: n! results.

Version A — used[] boolean array

private void backtrack(int[] nums, boolean[] used, List<Integer> path) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }

    for (int i = 0; i < nums.length; i++) {     // loop from 0 — order MATTERS here
        if (used[i]) continue;

        used[i] = true;
        path.add(nums[i]);

        backtrack(nums, used, path);

        path.remove(path.size() - 1);
        used[i] = false;                        // BOTH undos required
    }
}

Loop from 0, not start. Subsets use start to prevent reorderings; permutations want reorderings, so every unused element is fair game at every position.

Both undos are required. Forgetting used[i] = false means an element stays marked forever and later branches silently lose options.

Version B — in-place swapping

private void backtrack(int start, int[] nums) {
    if (start == nums.length) { res.add(toList(nums)); return; }
    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);           // put nums[i] in position `start`
        backtrack(start + 1, nums);
        swap(nums, start, i);           // swap back
    }
}

O(1) extra space beyond recursion. But it scrambles the array order during recursion, so the sorted-adjacency dedup trick doesn't apply.

For "permutations with duplicates", use Version A with sorting plus:

if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

The !used[i-1] clause means "the previous equal element isn't currently in the path", i.e. we're at the same tree level — the permutation analogue of i > start.

Family 4 — grid backtracking (Word Search)

Find whether a word can be spelled by adjacent cells, never reusing a cell.

private boolean dfs(char[][] board, int r, int c, String word, int i) {
    if (i == word.length()) return true;                    // consumed the whole word
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
    if (board[r][c] != word.charAt(i)) return false;        // wrong character

    char tmp = board[r][c];
    board[r][c] = '#';                       // mark as used ON THE CURRENT PATH

    boolean found = dfs(board, r + 1, c, word, i + 1)
                 || dfs(board, r - 1, c, word, i + 1)
                 || dfs(board, r, c + 1, word, i + 1)
                 || dfs(board, r, c - 1, word, i + 1);

    board[r][c] = tmp;                       // RESTORE — this is the backtrack
    return found;
}

Backtracking vs. flood fill — the distinction that matters

Both mark cells. The difference is whether you undo the mark:

Confusing the two turns a backtracking problem into a wrong flood fill (or vice versa). See 16 — Graphs.

In-place marking costs O(1) space versus a boolean[m][n] — and the restore line is the backtrack. Mention that you're mutating the input and confirm it's acceptable.

Family 5 — partitioning (Palindrome Partitioning)

Split a string so every piece is a palindrome. The choices are "where to cut next".

private void backtrack(String s, int start, List<String> path) {
    if (start == s.length()) { res.add(new ArrayList<>(path)); return; }   // consumed it all

    for (int end = start; end < s.length(); end++) {
        if (!isPalindrome(s, start, end)) continue;      // PRUNE invalid cuts
        path.add(s.substring(start, end + 1));
        backtrack(s, end + 1, path);                     // continue after the cut
        path.remove(path.size() - 1);
    }
}

private boolean isPalindrome(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

Trace on "aab":

start=0
├─ "a"   (0..0) ✓ palindrome
│  └─ start=1
│     ├─ "a"  ✓  → start=2 → "b" ✓ → ["a","a","b"] ✓
│     └─ "ab" ✗ not a palindrome
└─ "aa"  (0..1) ✓
│  └─ start=2 → "b" ✓ → ["aa","b"] ✓
└─ "aab" ✗

Result: [["a","a","b"], ["aa","b"]]. ✓

Optimization to offer: precompute boolean[n][n] isPal with DP so the check becomes O(1) instead of O(n). Get the base version working first.

Family 6 — constraint satisfaction (N-Queens)

Place n queens on an n×n board so none attack each other (no shared row, column, or diagonal).

Structural simplification: place exactly one queen per row. Row conflicts then become impossible by construction, and you only need to check columns and diagonals.

The diagonal identities

r - c is CONSTANT along a "\" diagonal
r + c is CONSTANT along a "/" diagonal

Check it on a 4×4 grid — for cells (0,0), (1,1), (2,2), r - c is 0 for all three. For (0,3), (1,2), (2,1), (3,0), r + c is 3 for all four.

That turns an O(n) diagonal scan into an O(1) set lookup. Memorize these; they recur in matrix problems generally.

private Set<Integer> cols = new HashSet<>();
private Set<Integer> diag = new HashSet<>();      // r - c
private Set<Integer> antiDiag = new HashSet<>();  // r + c

private void backtrack(int row, int n, char[][] board, List<List<String>> res) {
    if (row == n) { res.add(build(board)); return; }     // all rows filled

    for (int col = 0; col < n; col++) {
        if (cols.contains(col) || diag.contains(row - col) || antiDiag.contains(row + col)) continue;

        cols.add(col); diag.add(row - col); antiDiag.add(row + col);
        board[row][col] = 'Q';

        backtrack(row + 1, n, board, res);

        cols.remove(col); diag.remove(row - col); antiDiag.remove(row + col);
        board[row][col] = '.';
    }
}

Every piece of state applied before the recursive call is undone after it — four applications, four undos. Keeping them visually paired is how you avoid missing one.

Family 7 — Cartesian product (Letter Combinations)

The pure "one choice per position" shape — no pruning, no dedup.

private static final String[] MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

private void backtrack(String digits, int i, StringBuilder sb, List<String> res) {
    if (i == digits.length()) { res.add(sb.toString()); return; }

    for (char c : MAP[digits.charAt(i) - '0'].toCharArray()) {
        sb.append(c);
        backtrack(digits, i + 1, sb, res);
        sb.setLength(sb.length() - 1);          // UN-CHOOSE
    }
}

sb.setLength(sb.length() - 1) is the StringBuilder un-choose — the same role as path.remove(path.size() - 1).

Edge case to name: empty input should return an empty list, not [""]. Guard it explicitly.

Indices 0 and 1 in MAP are empty strings because phone keypads have no letters on those keys — using the digit directly as an index keeps the lookup clean.

Generate Parentheses — pruning by rule

Filed under Stack in NeetCode, but structurally it's backtracking with two constraints.

private void backtrack(int open, int close, int n, StringBuilder sb, List<String> res) {
    if (sb.length() == 2 * n) { res.add(sb.toString()); return; }

    if (open < n) {                             // can still open a new pair
        sb.append('(');
        backtrack(open + 1, close, n, sb, res);
        sb.setLength(sb.length() - 1);
    }
    if (close < open) {                         // can only close what's already open
        sb.append(')');
        backtrack(open, close + 1, n, sb, res);
        sb.setLength(sb.length() - 1);
    }
}

close < open is the entire correctness argument. It makes generating an invalid string impossible, so no validity filter is ever needed — every leaf is a valid answer.

The brute force generates all 2^(2n) strings and filters. Name it, then reject it: "instead of generating and checking, I'll make invalid states unreachable."

Pruning — where the real speedup lives

The skeleton is mechanical. Pruning is the engineering. Four kinds, roughly by value:

1. Feasibility — the remaining budget can no longer reach the target.

if (remaining < 0) return;

2. Ordering — sort first so you can break instead of continue:

Arrays.sort(candidates);
for (int i = start; i < candidates.length; i++) {
    if (candidates[i] > remaining) break;    // sorted: everything after is also too big
    ...
}

break kills the whole rest of the loop; continue only skips one. On sorted input, break is strictly better.

3. Symmetry / dedup — the i > start skip; start indices forbidding revisits.

4. Constraint propagation — the N-Queens sets: reject in O(1) rather than scanning.

Say which prunes you're applying and what each eliminates. "Sorting lets me break rather than continue, which cuts the branching factor" is exactly the kind of remark that lands.

Complexity

Backtracking complexity = (number of nodes in the decision tree) × (work per node). The work per node is usually the O(n) copy into the results list.

How to talk about exponential complexity

Don't apologize for it. Reframe:

"The output alone has 2^n subsets, so no algorithm can beat exponential here — producing the answer takes that long. The goal isn't to avoid exponential; it's to avoid exploring branches that produce nothing."

That reframes exponential cost as inherent to the problem rather than a failure of your solution, and shifts the conversation to pruning — where you actually have something to say.

Recognition checklist

Debugging checklist

1. Are you copying into the results list? new ArrayList<>(path).
2. Is every choice undone? Count applications and undos — they must match.
3. Is the dedup i > start and not i > 0?
4. Did you sort before deduping?
5. Does the base case fire before the loop can index out of bounds?
6. Is start/i+1/i right? i allows reuse, i + 1 forbids it, 0 allows reordering.