31

Backtracking

Choose, explore, un-choose: a disciplined way to try every possibility — and skip the hopeless ones early.

intermediate~90 min7 simulations13 problems

▶ guided lesson⚡ 1-minute summary↻ 14 recall cards

before this: Recursion · Arrays & Strings · Big-O

01 · why it exists

Why this exists, and the weight it carries

since1950s–1965

Backtracking (choose → explore → un-choose)

D. H. Lehmer or R. J. Walker (the name); Solomon W. Golomb & Leonard D. Baumert

Who named it is disputed. Golomb and Baumert (1965) say the mathematician D. H. Lehmer named it "backtrack"; Knuth (1975) credits R. J. Walker, who "aptly called" it backtracking. In 1960 Walker published a short note describing it as a general method for combinatorial problems. As Knuth tells it, Walker's 1950s n-queens program already kept the attacked columns and diagonals as bit vectors. In 1965 Golomb and Baumert's "Backtrack Programming" (Journal of the ACM) set the method out with many examples — and, Knuth notes, already suggested branching first on the choice with the fewest options left.

the problem it solvedSearching enormous spaces of combinations on early computers without building every complete candidate first.

its jobs today

  • SAT solvers — used to check chip designs and to solve scheduling and configuration puzzles — run a backtracking search (the DPLL procedure) with very smart pruning and learning.
  • Regex engines: Java's java.util.regex tries one way to match a pattern and backtracks to the next way when the rest fails — which is why some patterns blow up on long inputs.
  • Puzzle and game search: Sudoku apps, crossword fillers and game-tree search all grow a partial solution and undo it at a dead end.

the weight it carries

Illustrative: 8 queens on a chessboard. Any 8 of the 64 squares: C(64, 8) = 4,426,165,368 boards. One queen per row: 8⁸ = 16,777,216. One per row and column: 8! = 40,320. Backtracking with O(1) attack checks makes just 2,057 calls (counted with this chapter's N-Queens code) and finds all 92 solutions.

without it

Every "find all" or "place under rules" problem would mean building every complete candidate and checking it at the end — billions of boards instead of two thousand calls.

when · why · how

when
You must list every answer, or place items under rules, and n is small: about 20 for 2ⁿ, about 10 for n!.
why
When the output itself is exponential nothing is faster; backtracking spends its time only on partial answers that can still succeed. Cost = nodes × work per node; extra space = depth.
how
A recursive method over shared state: if (goal) { result.add(new ArrayList<>(path)); return; } then for each choice path.add(x); backtrack(…); path.remove(path.size() - 1);.

02 · plain english

The idea in 30 seconds

Build an answer one choice at a time. After each choice, recurse to make the next one.

When a branch is finished (or hopeless), undo the last choice and try the next option. That undo is the "back" in backtracking.

It is DFS over a decision tree you never build in memory — and pruning cuts whole subtrees you can prove are useless.

picture this

Solving a Sudoku in a phone app: pencil in a digit and move to the next cell. The moment a row breaks, tap Undo back to your last guess and try its next digit. You never look at every possible grid — Undo plus "this already breaks a rule" does all the work.

03 · remember

What you must know

  • The template: if (goal) record; for each choice: choose → recurse → un-choose. Almost every backtracking problem is this loop with a different goal, choice list and pruning rule.
  • State must be restored exactly. Whatever you change before the recursive call (path, used[], board cell) you undo right after it. Forget one piece and later branches see garbage.
  • Record a copy. result.add(new ArrayList<>(path)) — adding path itself stores a reference that you will empty later.
  • Three shapes: subsets (each element in or out → 2ⁿ), combinations (choose from start onward so order doesn't matter), permutations (choose any unused element → n!).
  • Duplicates: sort first, then at the same depth skip a value equal to its left neighbour: if (i > start && a[i] == a[i-1]) continue;.
  • Pruning is where the speed comes from: sort and break when a value overshoots, track counts (open/close brackets), or use O(1) attack tables (N-Queens).
  • Complexity = (number of nodes) × (work per node). Typical results: O(n·2ⁿ) subsets, O(n·n!) permutations, O(b^d) for branching b and depth d.
  • Backtracking is only fast enough for small inputs (n ≲ 20 for 2ⁿ, n ≲ 10 for n!). If n is large, look for DP or greedy instead.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

The template — choose k of n

Choose → explore → un-choose, one number at a time, always in increasing order. Red ✗ branches are cut by the loop bound before any call is made.

loading simulation…
sim

Subsets — watch the decision tree grow

Each node is one subset. The path stack grows on *choose* and shrinks on *un-choose*. Magenta = where we are, violet = the current path, green = recorded.

loading simulation…
sim

Subsets II — sort, then skip duplicate branches

Red branches would rebuild subsets we already have. One `continue` removes them before they are ever explored.

loading simulation…
sim

Permutations — used[] decides what is still free

Every level tries all n numbers and skips the used ones. Depth d has n − d real choices, so there are n! leaves.

loading simulation…
sim

Combination Sum — one break prunes a whole fan

Nodes show the remaining target. Because the candidates are sorted, the first number that is too big ends the loop (red ✗).

loading simulation…
sim

N-Queens — place, explore, remove

One queen per row. Three boolean arrays (column, ↘ diagonal, ↙ diagonal) answer "is this square attacked?" in O(1).

loading simulation…
sim

Word Search — mark the path, un-mark on the way back

Backtracking on a grid: a cell joins the path ('#'), its neighbours are explored, and it is restored if the word can't continue.

loading simulation…

05 · cost

Time & space, explained

How big is the search tree?
AnswersTimeExtra space (excl. output)why
Subsets of n distinct items2ⁿO(n·2ⁿ)O(n)Every element is in or out → 2ⁿ subsets; copying each into the result costs up to n.
Permutations of n distinct itemsn!O(n·n!)O(n)n choices, then n−1, … → n! leaves; each leaf copies a path of length n.
Combinations: k of nC(n, k)O(k·C(n, k))O(k)One leaf per combination, each copied in O(k); the start index prevents re-ordering.
Branching b, depth d (phone letters, brackets)≤ bᵈO(d·bᵈ)O(d)A full tree with b children per node has bᵈ leaves; recursion is d frames deep.
Grid path search, word length L—O(m·n·3ᴸ)O(L)m·n start cells; after the first step each cell has at most 3 unvisited neighbours.
N-Queens with O(1) attack checks≪ n!O(n!)O(n)Row r has at most n − r free columns, so the tree is bounded by n!; pruning makes it far smaller in practice.
Sudoku with m empty cells1O(9ᵐ) worst caseO(m)Up to 9 digits per empty cell. Filling the cell with the fewest options first shrinks the real tree: under 100 calls on the judge's 26-clue puzzles.
Will it run in time? (≈10⁸ simple steps per second)
Comfortable nSteps at that nwhy
O(2ⁿ) / O(n·2ⁿ)n ≤ ~202²⁰ ≈ 10⁶ (×20 ≈ 2·10⁷)Each extra element doubles the work, so the limit arrives suddenly.
O(n!)n ≤ ~1010! ≈ 3.6·10⁶12! ≈ 4.8·10⁸ is already too slow; this is why LC 46 caps n at 6.
O(4ⁿ)n ≤ ~104¹⁰ ≈ 10⁶4ⁿ = 2²ⁿ — it behaves like 2ⁿ with twice the depth.
Constraints say n ≤ 10⁵——Backtracking is the wrong tool. Look for greedy, DP, two pointers or a heap.

06 · java

Raw vs Collections Framework

The universal template (LC 77 Combinations)

javachoose → explore → un-choosejava.util.*
class Solution {    public List<List<Integer>> combine(int n, int k) {        List<List<Integer>> result = new ArrayList<>();        backtrack(1, n, k, new ArrayList<>(), result);        return result;    }     private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> result) {        if (path.size() == k) { // goal: k numbers chosen            result.add(new ArrayList<>(path)); // record a COPY            return;        }        int need = k - path.size(); // numbers still to pick        for (int x = start; x <= n - need + 1; x++) { // stop while enough numbers remain            path.add(x); // choose            backtrack(x + 1, n, k, path, result); // explore: only larger numbers next            path.remove(path.size() - 1); // un-choose        }    }}
  • Five beats every time: goal? → for each choice → choose → explore → un-choose.
  • The loop bound x <= n - need + 1 is pruning: if fewer than need numbers remain, no branch can finish.
  • start is what makes this combinations (order ignored). Loop from 0 with a used[] instead and you get permutations.
  • Bas itna yaad rakho: every problem in this chapter is this method with a different goal test, choice list and pruning rule.

Keeping the path: ArrayList vs a fixed array

javaint[] + lengthjava.util.*
class PathArray {    /** Same search, but the path is a fixed int[] plus a length — un-choosing is free. */    static List<int[]> subsets(int[] nums) {        List<int[]> out = new ArrayList<>();        dfs(nums, 0, new int[nums.length], 0, out);        return out;    }     private static void dfs(int[] nums, int start, int[] path, int len, List<int[]> out) {        out.add(Arrays.copyOf(path, len));         // copy only the used prefix        for (int i = start; i < nums.length; i++) {            path[len] = nums[i];                   // choose: write slot `len`            dfs(nums, i + 1, path, len + 1, out);  // explore with a longer path            // un-choose: nothing to do — our own `len` never changed        }    }}
  • path.remove(path.size() - 1) removes the last element in O(1). Removing from the front would be O(n).
  • Careful: on a List<Integer>, remove(int) removes by index and remove(Object) by value. Always pass the index here.
  • With an int[] and a len parameter, un-choosing is free: the caller's len never changed, so the stale slot is simply ignored.
  • Either way, copy the path when you record it: new ArrayList<>(path) or Arrays.copyOf(path, len).

Remembering what's used: bitmask vs HashSet

javaint bitmaskjava.util.*
class UsedBitmask {    /** Permutations of a string's characters; bit i of `mask` = "index i is already used". */    static List<String> permutations(String s) {        List<String> out = new ArrayList<>();        dfs(s.toCharArray(), 0, new StringBuilder(), out);        return out;    }     private static void dfs(char[] chars, int mask, StringBuilder path, List<String> out) {        if (path.length() == chars.length) {            out.add(path.toString());            return;        }        for (int i = 0; i < chars.length; i++) {            if ((mask & (1 << i)) != 0) continue;     // index i already used            path.append(chars[i]);                    // choose            dfs(chars, mask | (1 << i), path, out);   // explore (new mask, ours untouched)            path.deleteCharAt(path.length() - 1);     // un-choose        }    }}
  • A boolean[] used (see Permutations) is the everyday choice: O(1), no boxing, easy to read.
  • A bitmask passes mask | (1 << i) by value — the caller's mask is untouched, so there is nothing to undo. Works for n ≤ 31 (int) or 63 (long).
  • A HashSet<Integer> works but boxes every index and hashes it — correct, just slower. Remember to undo both the set and the path.
  • StringBuilder.append + deleteCharAt(length() - 1) is the string version of add / remove-last; both are O(1).
Java API you will actually use
calldoescost
path.add(x)Choose: push onto the end of an ArrayListO(1) amortized
path.remove(path.size() - 1)Un-choose: pop the last element (by index!)O(1)
new ArrayList<>(path)Snapshot the path when recording an answerO(k)
sb.append(c) / sb.deleteCharAt(sb.length() - 1)Choose / un-choose a characterO(1) amortized
Arrays.sort(nums)Sort so duplicates are adjacent and pruning can breakO(n log n)
boolean[] used = new boolean[n]Which indices are already in the path (permutations)O(1) per check
mask | (1 << i), (mask >> i) & 1Bitmask: mark index i used / test itO(1)
free & -free, free &= free - 1Take the lowest free option out of a bitmask (N-Queens II, Sudoku)O(1)
Integer.bitCount(free)How many options a cell still has (pick the fewest first)O(1)
Arrays.fill(row, '.')Initialise a board row (N-Queens, Sudoku)O(n)
new String(charArray)Turn a board row into the String LeetCode expectsO(n)

Every subset / combination

→ Loop from start, recurse with i + 1

Each set is built in one canonical order, so it appears once.

Every ordering (permutation)

→ Loop from 0 with boolean[] used

Any unused element may come next; used prevents reuse.

An element may be reused (Combination Sum)

→ Recurse with i instead of i + 1

Staying on i allows picking it again; start still blocks re-ordering.

Input has duplicates, output must not

→ Sort + if (i > start && a[i] == a[i-1]) continue

Never generates a duplicate — far cheaper than a HashSet of results.

Grid path (word search, islands with a path)

→ Mark the cell in place ('#') and restore it

O(1) extra per cell, no visited array to allocate.

Just count or check existence

→ Return a number / boolean instead of collecting lists

Skips all the copying — and lets you stop at the first success.

Fill a board under rules (Sudoku, N-Queens)

→ int bitmask tables per row / column / box, fewest-options cell first

A check is one AND, the options are one bitCount, and forced cells get filled before any guessing.

07 · recognise

Spot the pattern

"Return all …" (subsets, permutations, combinations, partitions, valid strings)

Backtracking — the output itself is exponential, so nothing faster exists

Small constraints: n ≤ 10, 15, 20, a 9×9 board, words ≤ 15 letters

An exponential search is allowed; plan choose / explore / un-choose

"Place" items under constraints (queens, Sudoku digits, colours)

Backtracking with O(1) constraint tables for pruning

Find a path through a grid that spells / sums to something, cells used once

DFS + mark cell + restore (grid backtracking)

Input contains duplicates and output must be unique

Sort, then skip equal neighbours at the same depth

"Count the number of ways" or "minimum / maximum" with large n

Probably DP, not backtracking — overlapping subproblems give it away

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • result.add(path) instead of result.add(new ArrayList<>(path)) — every stored answer ends up as the same (empty) list.
  • Forgetting to undo one piece of state (e.g. resetting used[i] but not popping path, or not restoring a board cell).
  • path.remove(x) on a List<Integer> where x is an int — it removes index x, not value x.
  • Duplicate skip with i > 0 instead of i > start — that also skips valid answers like [1, 2, 2] in Subsets II.
  • Forgetting to sort before the duplicate skip or the break pruning — both rely on equal / larger values being adjacent.
  • In Combination Sum, recursing with i + 1 (no reuse) or 0 (every order counted again → duplicates).
  • Returning [""] instead of [] for empty input in Letter Combinations — check the empty case first.
  • Using a HashSet of results to fix duplicates: correct, but it still explores every duplicate branch and pays to hash each list.

tricks

  • Draw the decision tree for a tiny input (n = 3) before coding: what is a node, what are its children, when is it a leaf?
  • Name the three things out loud: state (path, used, board), choices at a node, goal test. The code follows.
  • Put pruning before the recursive call (break / continue), not at the start of the callee — it saves a whole call per pruned branch.
  • If you only need one answer (Sudoku, Word Search), make the function return boolean and stop as soon as it returns true.
  • Test with: empty input, a single element, all-equal elements, and the largest n in the constraints (to feel the exponential).
  • Mention complexity as answers × cost per answer — interviewers accept O(n·2ⁿ) for subsets because the output is that big.

09 · why & how

Questions you might be too shy to ask

What is the difference between backtracking and plain recursion / DFS?

Backtracking is DFS — over a tree of partial answers instead of an explicit graph. The extra ingredient is shared, mutable state (the path) that you change before recursing and undo after. Plain recursion often builds new copies instead, which is simpler but slower.

Why do I have to undo the choice? The recursive call already returned.

Because the path, used[] or board is one shared object for the whole search. When the call returns, the object still contains the choice you made. The next loop iteration must start from the same state as this one, so you remove it.

Where is the "going back" in the code? I don't see any jump.

There is no jump — it's just a function returning. Say path = [1] and the loop calls backtrack with [1, 2]. When that call finishes, Java continues at the line right after the call, inside the loop of the [1] frame. You remove the 2, so path = [1] again, and the loop moves on to try 3. Each frame keeps its own i and start, so it knows which option comes next.

Which changes do I have to undo, and which ones undo themselves?

Undo anything shared: the path list, used[], the board, a StringBuilder — every frame sees the same object. Nothing to undo for primitive arguments like start, remain - c[i] or mask | (1 << i): Java passes a copy, so the caller's value never changed. Simple hai — wrote it into an object? Undo it. Passed a new number as an argument? Done.

Why new ArrayList<>(path) when recording?

result.add(path) stores a reference. After backtracking finishes, path is empty again — so every entry in result would point at the same empty list. Copying freezes the current contents.

When do I record an answer — at every node, or only at the end? And do I return after?

Ask: is a partial path already an answer? Subsets: yes, every node is a subset — record on arrival and don't return, because its children are answers too. Permutations or k-combinations: only a full path counts — record when path.size() == n (or k) and return, since going deeper can't help. Combination Sum: record when remain == 0, then return.

How does the i > start && nums[i] == nums[i-1] skip work?

After sorting, equal values are neighbours. At one depth (one loop), choosing the first 2 or the second 2 leads to identical subtrees — so only the first is allowed. i > start keeps it legal to pick the second 2 at the next depth, which is how [2, 2] is still produced.

Permutations II: what does !used[i - 1] mean in the duplicate skip?

After sorting, equal values must be used left to right: the left copy before the right copy. If nums[i] == nums[i - 1] and the left copy is not in the path right now, picking the right copy here only swaps the two copies' roles — the same permutation again. So skip it. With [1, 2, 2] you get [2, 2, 1] once, not twice.

Subsets loop from start, permutations from 0. Why?

For subsets, {1, 2} and {2, 1} are the same answer, so we only build sets in increasing index order — choices start after the last index used. For permutations, [1, 2] and [2, 1] are different answers, so any unused element may come next.

When pruning, break or continue?

continue skips just this one choice; break skips this choice and every later one in the loop. Use break only when the input is sorted and later choices can only be worse — in Combination Sum (candidates c sorted), if c[i] > remain, every bigger number overshoots too. Use continue when only this choice is bad, like the duplicate skip or a used index. Not sure? continue is always correct, just slower.

How do I state the complexity without panicking?

Count the leaves (or all nodes) of the decision tree, then multiply by the work done per node — usually the O(n) copy at the leaves. Subsets: 2ⁿ nodes × O(n) = O(n·2ⁿ). Permutations: n! leaves × O(n) = O(n·n!). Space is the recursion depth plus the path: O(n), not counting the output.

When should I switch from backtracking to DP?

When the question asks for a count or an optimum (not the list of answers) and the same sub-question repeats — e.g. "how many combinations sum to target" is Coin Change II, a DP. If you must list every answer, backtracking is unavoidable because the output itself is exponential.

I freeze when a problem says "return all …". How do I even start?

Answer three questions on paper before any code. State: what does a partial answer look like (a path, a board)? Choices: what can I add next from here? Goal: when is a path a full answer? Then drop the three answers into the template: goal → loop over choices → choose → explore → un-choose. Chalo, dry-run it on n = 3 — the tree is tiny, and once it works there, it works everywhere.

Is it bad that my solution is exponential?

Not when the problem asks for all answers — no algorithm can print 2ⁿ subsets in less than 2ⁿ steps. What the interviewer checks is that you don't waste work: no duplicate branches, no dead branches you could prune, no copying except when recording.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #78
    Subsetsmust-do
    MediumBloombergAmazonMetaMicrosoftGoogle+1
  2. #77
    Combinationsmust-do
    MediumMetaAmazonGoogleMicrosoft
  3. #90
    Subsets IImust-do
    MediumBloombergGoogleAmazonMeta
  4. #46
    Permutationsmust-do
    MediumLinkedInAmazonMicrosoftBloombergGoogle+1
  5. #39
    Combination Summust-do
    MediumWalmartByteDance / TikTokAirbnbAmazonMicrosoft+1
  6. #40
    Combination Sum II
    MediumMetaMicrosoftAmazonGoogle
  7. #17
    Letter Combinations of a Phone Number
    MediumLinkedInAmazonUberMicrosoftMeta+1
  8. #22
    Generate Parenthesesmust-do
    MediumWalmartAmazonBloombergMicrosoftGoogle+1
  9. #79
    Word Searchmust-do
    MediumUberBloombergByteDance / TikTokNetflixPayPal+1
  10. #131
    Palindrome Partitioning
    MediumBloombergAmazonMetaGoogle
  11. #51
    N-Queensmust-do
    HardByteDance / TikTokAmazonMicrosoftGoogleMeta
  12. #52
    N-Queens II
    HardAmazonMicrosoftGoogle
  13. #37
    Sudoku Solver
    HardAmazonMicrosoftGoogle

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #212
    Word Search II
    Hardin Tries

    Word Search for many words at once: the same grid backtracking, walking a trie instead of one word.

  2. #377
    Combination Sum IV
    Mediumin Dynamic Programming

    Count the ways instead of listing them — the moment backtracking turns into DP.

  3. #36
    Valid Sudoku
    Mediumin Hashing

    The row / column / box tables of Sudoku Solver, used once to check a board.

  4. #31
    Next Permutation
    Mediumin Arrays & Strings

    The next ordering in O(n), with no backtracking at all.

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    DFS over a tree of partial answers: choose a piece, explore the rest, un-choose it. The undo lets one shared path serve every branch.

  2. use it when

    "Return all …" (subsets, orders, partitions, boards) or "place under rules", with small n: about 20 for 2ⁿ, about 10 for n!.

  3. template

    if (goal) { record a copy; return; } then for (choice) { choose; backtrack(next); un-choose; }

  4. cost

    Nodes × work per node. Subsets O(n·2ⁿ) · permutations O(n·n!) · k of n O(k·C(n, k)). Extra space = depth, O(n).

  5. trap

    result.add(path) stores a reference that ends up empty. Always result.add(new ArrayList<>(path)).

  6. trap

    Duplicates: sort, then if (i > start && a[i] == a[i - 1]) continue;. With i > 0 you lose answers like [1, 2, 2].

  7. pro tip

    Order ignored → loop from start. Order matters → loop from 0 with used[]. Reuse allowed → recurse with i, not i + 1.

  8. pro tip

    Prune before the call: sort + break, a loop bound, O(1) attack tables. Need one answer? Return boolean and stop on true.

  9. use it when

    Asked to count or find a min/max, with n in the hundreds or more? That's DP, not backtracking.

12 · recall

Flip, remember, repeat

card 1 / 14
recall

Why record new ArrayList<>(path) and not path itself?

tap or Space to flip ↻

Question 1: Why record new ArrayList<>(path) and not path itself?

13 · check yourself

Quick quiz

  1. Why does `result.add(path)` produce a list of empty lists at the end?

  2. Subsets of [1, 2, 3]: the loop starts at `start` instead of 0. What does that guarantee?

  3. Sorted nums = [1, 2, 2]. In Subsets II, which branch is skipped?

  4. Combination Sum lets each number be reused. Which recursive call achieves that?

  5. What is the time complexity of generating all permutations of n distinct numbers?

  6. In N-Queens, squares (1, 3) and (2, 2) share which diagonal id?

  7. A problem asks for the **number** of ways to reach a target sum, with n = 1000. Best tool?

  8. Combinations with n = 5, k = 3. The path is [1] (need 2 more). What is the last x the loop tries?

  9. Your Sudoku solver fills the board, but the final board comes back with '.' in it again. Most likely cause?

0/0 correct · 9 left

14 · learn more

A second teacher, if you want one