Backtracking Problems

Eight classic interview problems — Subsets, Subsets II, Combination Sum, Permutations, Word Search, Palindrome Partitioning, Letter Combinations of a Phone Number and N-Queens — solved from zero with one idea: make a choice, explore everything that can follow it, then undo the choice and try the next one. For each problem you will see the slow obvious idea, the pseudocode, the Dart code, and an animation you can feed your own input that draws the tree of choices as it grows and shrinks, with the current path highlighted, dead branches greyed out, and every recorded answer listed. By the end you will own one template, know when to copy the path, how to skip repeated answers, how to cut branches early, and how to state the running time honestly by counting the answers.

Choose, explore, un-choose: the decision tree and the template

Some problems ask for every arrangement that obeys a rule: all groups you can pick, all orders, all ways to cut a word, all boards with eight safe queens. There is no clever formula; you have to build each answer piece by piece. Backtracking is the tidy way to build them all without missing one and without building one twice. A few words first:

• A choice is one small decision: "take the number 3", "put the next queen in column 2", "cut the word after the second letter".
• The path is the list of choices made so far. It is a partly built answer.
• The decision tree is a picture of every possible run. The root (top) is "nothing chosen yet". Each line going down is one choice, and each box (a node) is the situation after the choices on the way to it. A node with no children is a leaf.
• A depth-first walk goes as deep as it can down one branch before it tries the next branch — exactly the maze walker. Backtracking is a depth-first walk of the decision tree.
• Recursion means a function that calls itself. Each call handles one node of the tree; the computer keeps the unfinished calls on the call stack (a pile of "where was I?" notes). If that is new, read D07 · Functions, Closures & the Call Stack first — the recursion animation there is the same machinery.

The three moves

1. Choose. Add one choice to the path (path.add(x)), and update any bookkeeping (a "used" flag, a remaining sum, a set of attacked columns).
2. Explore. Call the function again for the next decision. That call explores the whole part of the tree below this choice and comes back.
3. Un-choose. Undo exactly what step 1 did (path.removeLast(), clear the flag). Now the state is the same as before the choice, so the next choice starts clean.

The un-choose step is what makes it "back"-tracking: one single path list is shared by the whole walk, and it grows on the way down and shrinks on the way back up. In the animations below you will see the highlighted route in the tree do exactly that.

The template

Almost every solution on this page has these parts. Learn this shape once and each problem only fills in the blanks:

result ← empty list
path ← empty list                       // the choices made so far
backtrack(state):
    if path is a complete answer:       // the base case
        add a COPY of path to result
        return                          // (some problems keep going instead)
    for each choice allowed in this state:
        if the choice cannot lead to an answer:
            skip it                     // pruning
        choose it                       // path.add, mark as used, …
        backtrack(the state after the choice)
        un-choose it                    // path.removeLast, unmark, …
backtrack(the starting state)
return result

The state is whatever tells the next call which choices are still allowed:

• A start index when order does not matter (Subsets, Combination Sum). Only items at or after start may be chosen, so [1, 3] is built but [3, 1] never is — each group appears exactly once.
• Used flags when order matters (Permutations). Any item may come next, as long as it is not already in the path.
• A position in a string, a grid or a board (Palindrome Partitioning, Letter Combinations, Word Search, N-Queens).

Pruning: cut dead branches early

Pruning means refusing a choice as soon as you can prove that nothing below it can become an answer. A greyed-out node in the animations is a pruned branch: the code looked at it, said "no", and never walked into it. One good pruning test can remove most of the tree. Examples on this page: "the remaining sum is smaller than this candidate" (Combination Sum), "this first piece is not a palindrome" (Palindrome Partitioning), "this square is attacked" (N-Queens), "this letter does not match" (Word Search). Pruning never changes the answers — only how many dead ends you visit.

Copy the path when you record it

Here is the most common Dart backtracking bug. In Dart a List is an object that lives on the heap (the shared storage room for objects); a variable only holds a reference to it — an arrow pointing at the box. result.add(path) does not store the numbers that are in the path right now. It stores another arrow to the very same box. The walk keeps changing that box, and at the end it is empty again — so every entry of result shows an empty list. The fix is one line: result.add([...path]) creates a new list with the same items (a snapshot). Watch both versions in memory:

Count the answers to state the running time honestly

A backtracking function prints or returns every answer, so it can never be faster than the number of answers times the cost of writing one down. Count them first — that number usually is the running time:

These numbers explode: 2ⁿ doubles with every extra item, and n! grows even faster (20! is about 2.4·10¹⁸). That is why backtracking problems come with tiny limits like n ≤ 10 or n ≤ 16 — the limit itself is a hint that an exponential answer is expected. The counting rules behind 2ⁿ, n! and C(n, k) are explained from zero in M02 · Counting & Probability. When a problem only asks how many or the best one (not the full list), the same tree often has many repeated subtrees, and dynamic programming (C15 · Dynamic Programming) can be far faster — question p12-q26 shows the difference.

Repeated values: sort, then skip equal neighbours at the same depth

If the input contains equal values, the plain template builds some answers twice: from [1, 2, 2] it builds [1, 2] once with the first 2 and once with the second 2. The standard cure has two parts:

1. Sort the input, so equal values sit next to each other.
2. In the loop over choices, skip a value that equals the previous choice tried at the same depth: if (i > start && a[i] == a[i - 1]) continue;. "At the same depth" is what i > start means — the first copy in this loop is always allowed (so [2, 2] can still be built by going deeper), but a second copy as an alternative for the same slot would only repeat the first copy's whole subtree.

For permutations the same idea uses the used flags instead: copy i of a value may be placed only after copy i − 1 is already in the path (question p12-q13). Removing repeats afterwards with a Set also gives the right answer, but it builds every repeat first — on [2, 2, 2, 2, 2, 2, 2, 2] that is 40 320 permutations to produce one.

Subsets

The task. You get a list nums of whole numbers that are all different. Return every subset — every group you can form by keeping some of the numbers and dropping the rest, including the empty group and the whole list. The order of the subsets, and the order inside each subset, do not matter, but no subset may appear twice.

Brute force. Count from 0 to 2ⁿ − 1 and read each number in binary: bit i equal to 1 means "take nums[i]". The number 5 is 101 in binary, so it means "take items 0 and 2". This is not slow — it already costs O(n · 2ⁿ), the size of the answer — but it cannot skip anything, so it does not stretch to the harder problems below, where whole groups of choices must be cut off or repeats avoided.

Key insight. Build each subset by choosing the next item to add, only from items to the right of the last one added. The state is a start index: after adding nums[i], the next call may only add from i + 1 on. In the tree, every node is a valid subset (the path to it), so we record a copy at every node, not only at the leaves. The start index is what prevents repeats: [1, 3] is built (3 is right of 1) but [3, 1] never is.

Why it is correct. Each subset, written in index order, is exactly one route from the root: add its first item, then its second, and so on — each one to the right of the previous. So every subset is reached once, and nothing else is reached. Two subsets with different items end at different nodes.

An edge case: the empty list. The root records the empty subset, the loop has nothing to choose, and the answer is [[]] — one subset, not zero.

Complexity. Time O(n · 2ⁿ) — the tree has exactly 2ⁿ nodes (one per subset), and recording a node copies up to n numbers. Extra space O(n) — one path of length ≤ n and at most n + 1 calls on the stack; the output itself takes O(n · 2ⁿ).

Input size → what is feasible: n = 16 → 65 536 subsets, about a million copied numbers: instant. n = 25 → 33 million subsets: listing them is already too much memory, which is why such tasks keep n small.

Follow-ups interviewers ask. The list has repeated values — next problem. Only subsets of size exactly k (combinations, p12-q1). Only subsets with a given sum (p12-q10) — prune when the sum overshoots. Return them without recursion (the bit-mask brute force, or an explicit stack, p12-q28). Return them in increasing order of size (a breadth-first version). The k-th subset in a fixed order without building the others.

The idea underneath: recursion and the call stack in D07 · Functions, Closures & the Call Stack, binary numbers in D03 · Numbers & Bits, and counting 2ⁿ in M02 · Counting & Probability.

Subsets II (with repeated values)

The task. Same as Subsets, but nums may contain equal values. Two groups with the same values (counted with how many times each appears) are the same subset, and must be returned only once. Order does not matter.

Brute force. Build all 2ⁿ subsets as before, sort each one, and keep it only if its sorted form has not been seen yet (a Set of keys). Correct, but it builds every repeat first: [3, 3, 3, 3, 3, 3, 3, 3] builds 256 groups to keep 9.

Key insight. Sort first, so equal values are neighbours. Then, inside the loop of one call, use only the first copy of each value: if (i > start && a[i] == a[i - 1]) continue;. At one node, choosing the first 2 or the second 2 as "the next item" leads to identical subtrees, so the second one is a pruned branch. Deeper calls start their own loop, where the next copy is again "first in this loop" — so [2, 2] is still built, by going one level down.

Why it is correct. Write any subset in sorted order. Among equal values, insist that it always uses the earliest copies available. That gives each different subset exactly one route, and the skip rule allows exactly those routes: a route that uses a later copy while skipping an earlier equal one at the same level is the one being refused.

An edge case: every value is equal. Only the first branch at each level is allowed; all others are pruned, and the tree becomes a single chain: 0, 1, 2 or 3 copies.

Complexity. Sorting is O(n log n). The tree has one node per different subset, plus at most one greyed node per skipped copy, so time is O(n · 2ⁿ) in the worst case (all values different) and much less with many repeats. Extra space O(n).

Input size → what is feasible: n = 16 with all different values → 65 536 subsets, instant; sixteen equal values → only 17 subsets and 17 nodes, where the Set approach would still build 65 536.

Follow-ups interviewers ask. Combination Sum II — each item at most once, repeats in the input (p12-q12): the same skip rule plus a sum. Permutations with repeats (p12-q13). Count the different subsets without listing them: multiply (count of each value + 1).

The idea underneath: the Subsets tree above with one pruning rule; sorting from C02 · Insertion & Merge Sort and why two lists are not == in D29 · Object (==, hashCode).

Combination Sum (numbers may be reused)

The task. You get a list candidates of different positive whole numbers and a positive target. Return every group of candidates whose sum is exactly target. The same candidate may be used as many times as you like. Two groups are the same if they use the same numbers the same number of times, whatever the order; return each group once.

Brute force. For each candidate decide how many copies to take — from 0 up to target ÷ candidate — and turn through every combination of counts like a car's odometer, keeping those whose sum is right. With the candidates 2, 3, 5, 7 and target 40 that is 21 · 14 · 9 · 6 ≈ 16 000 count vectors, most of them hopeless.

Key insight. Backtrack with two pieces of state: a start index (to build each group in non-decreasing order, so it appears once) and the remaining amount. Two changes from Subsets:

• After choosing candidates[i], recurse with i — not i + 1 — because the same number may be taken again.
• Sort the candidates. When candidates[i] > remaining, that branch overshoots, and so does every later (bigger) candidate: break out of the loop, pruning them all at once.

The base case is remaining == 0: the path sums to the target, so record a copy and stop going deeper (adding more positive numbers can only overshoot).

Why it is correct. Any valid group, written in non-decreasing order, is one route: its first number, then its second (same index or later), and so on. The start index allows exactly the non-decreasing routes, so each group appears once. Pruning only removes branches whose sum would pass the target, which contain no answers.

An edge case: no solution. Every branch is pruned or runs out, the tree is tiny, and the result is an empty list.

Complexity. Let T = target and m = the smallest candidate. The tree is at most T / m levels deep, and a node has at most n children, so the bound is O(n^T/m) nodes, times T / m to copy each answer. That bound is loose; what you can promise honestly is "proportional to the number of nodes visited", and pruning keeps that close to the number of answers. Extra space O(T / m) for the path and the call stack.

Input size → what is feasible: target ≤ 40 with candidates ≥ 2 → at most 20 levels, a few thousand calls. With a candidate of 1 the depth is the target itself and the answers explode — then counting the groups (not listing them) is a dynamic-programming job (the coin change problem).

Follow-ups interviewers ask. Each candidate at most once and repeats in the input (p12-q12). Exactly k distinct digits 1..9 (p12-q8). Only the number of groups — the coin change counting problem, solved by dynamic programming (C15 · Dynamic Programming). Order matters ("how many sequences sum to T") — a different count, also DP.

The idea underneath: the start-index template from the opening section plus pruning on a sorted list; sorting in C02 · Insertion & Merge Sort.

Permutations

The task. You get a list nums of different whole numbers. Return every permutation — every order in which the numbers can be lined up, each number used exactly once. The order of the permutations in the result does not matter.

Brute force. Write every sequence of n indexes, each from 0 to n − 1 (nⁿ sequences), and keep those that use each index once. For n = 8 that is 16.7 million sequences to keep 40 320 — most of the work is wasted on sequences like [0, 0, 3, …].

Key insight. Here order matters, so a start index is wrong (it would never put 3 before 1). Instead each level fills the next position with any number not used yet, tracked by a used list of true/false flags — that check prunes the repeated-index sequences before they are built. The answer is complete when the path has n items. Choose = set the flag and add; un-choose = remove and clear the flag.

Why it is correct. The first level tries every number in the first position. Below each choice, the same procedure lists every order of the remaining numbers (by the same argument, one level smaller). Every permutation is one route, and no route repeats a number because of the flags.

An edge case: a single number. The root chooses it, the path is full, and the one permutation is recorded.

Complexity. The tree has n! leaves and about e · n! ≈ 2.7 · n! nodes in total. Each node runs a loop of n, and each leaf copies n numbers, so time is O(n · n!). Extra space O(n): the path, the flags and n + 1 calls on the stack.

Input size → what is feasible: n = 8 → 40 320 orders, instant; n = 11 → about 40 million, already too many to store; n = 20 → 2.4·10¹⁸, impossible to list. Problems that need "the k-th order" or "the next order" avoid listing (p12-q29, p12-q31).

Follow-ups interviewers ask. With repeated values (p12-q13). Permutations in increasing (dictionary) order without recursion (p12-q29). The k-th permutation directly (p12-q31). Arrangements where position and value must divide each other (p12-q16). Letter case permutations (p12-q5).

The idea underneath: the template with used flags instead of a start index; n! from M02 · Counting & Probability.

Word Search

The task. You get a grid of letters and a word. Return true if the word can be spelled by a path of cells where each next cell is directly above, below, left or right of the previous one (not diagonal), and no cell is used twice in the same path. Otherwise return false.

Brute force. Try every sequence of L cells and check that neighbours touch, letters match and no cell repeats — (rows · cols)^L sequences, hopeless even for a small grid. A smarter exhaustive method keeps a set of "states" (where the path ends, and which cells it has used) and grows them one letter at a time. It is correct, and we use it to test the main solution, but the number of states can still be exponential and every state carries a bit set:

Key insight. Backtracking on the grid. dfs(r, c, k) answers "can word[k..] be spelled starting at cell (r, c)?". It fails at once if the cell is outside the board or its letter is not word[k] — that is the pruning, and it happens on the very first letter for most cells. On a match it marks the cell (writes '#' over it, so it can never match again in this path), tries the four neighbours for k + 1, and then restores the letter before returning — the un-choose step. The outer loop starts the search from every cell.

Why it is correct. Every valid path is found: the outer loop tries its first cell, and at each step dfs tries every neighbour, including the right one. No invalid path is accepted: letters are checked, neighbours are the only moves, and a marked cell cannot be reused because '#' matches no letter. Restoring keeps the board exactly as it was for all the other attempts.

An edge case: the letters are all there, but the word would need a cell twice. The mark on the starting cell blocks the return to it, so the answer is false.

Complexity. From each of the rows · cols starting cells, the first step has at most 4 directions and every later step at most 3 (the cell it came from is marked). So time is O(rows · cols · 4 · 3^{L − 1}) = O(rows · cols · 3^L). Extra space O(L) for the recursion; marking in place needs no visited grid.

Input size → what is feasible: a 6 × 6 grid and a 15-letter word: the bound is huge, but mismatching letters stop almost every branch after one or two steps. Bad cases are grids full of one letter with a word like AAAAAAAAB; counting the letters first (does the grid even contain enough of each?) and searching from the rarer end of the word fixes most of them.

Follow-ups interviewers ask. Many words at once — build a trie (a prefix tree) of the words and walk the grid once (p12-q21; the trie itself is taught in Step 13.8 · Trie & Heap Problems). Count every path that visits all empty cells exactly once (p12-q30). Return the path itself. Allow diagonal moves (8 neighbours).

The idea underneath: depth-first search on a grid — the same walk as in Step 13.9 · Graph Problems and C22 · BFS, DFS, Topological Sort, with one change: here a cell is unmarked on the way back, because another path may need it.

Palindrome Partitioning

The task. A palindrome reads the same forwards and backwards ("level", "aa", any single letter). You get a string s. Cut it into pieces so that every piece is a palindrome, and return every way to do that. Each answer is the list of pieces in order; the order of the answers does not matter.

Brute force. A string of length n has n − 1 gaps between letters, and each gap is cut or not: 2^{n − 1} cuttings, numbered by the bits of a counter. For each, split the string and check that every piece is a palindrome. It always does the full work, even when the very first piece already fails.

Key insight. Decide the pieces from left to right. The state is start, where the next piece begins. The choices are the piece's end: s[start..end] for every end from start to n − 1. If that first piece is not a palindrome, prune it — no completion can rescue it. Otherwise add it to the path and solve the rest from end + 1. When start reaches the end of the string, the path covers everything: record a copy.

Why it is correct. Every valid cutting has a first piece, which is a palindrome, so it is one of the choices tried at the root; below it, the rest of the string is cut by the same procedure. Pruning only removes cuttings whose first piece is not a palindrome, and those are never answers.

An edge case: all letters equal. Every piece is a palindrome, nothing is pruned, and the tree shows all 2^{n − 1} cuttings.

Complexity. In the worst case (all letters equal) there are 2^{n − 1} answers, each built with palindrome checks of total length n, so time is O(n · 2ⁿ). Extra space O(n) for the path and the stack. A table isPal[i][j] filled once in O(n²) makes every later check O(1) — it does not change the worst case, which is dominated by writing down the answers.

Input size → what is feasible: n = 16 → at most 32 768 answers, instant. If only the fewest cuts are needed, the answer is a single number and dynamic programming finds it in O(n²) for n in the thousands.

Follow-ups interviewers ask. The fewest cuts so that every piece is a palindrome (dynamic programming). Cut a string into dictionary words — every sentence (p12-q24). Cut a digit string into four valid address parts (p12-q14).

The idea underneath: the same start-index template, with substrings as choices; palindrome checking with two pointers in Step 13.2 · Two Pointers and Dart strings in D04 · Strings.

Letter Combinations of a Phone Number

The task. On an old phone keypad each digit from 2 to 9 stands for a few letters: 2 → abc, 3 → def, 4 → ghi, 5 → jkl, 6 → mno, 7 → pqrs, 8 → tuv, 9 → wxyz. Given a string of such digits, return every word you can type by picking one letter for each digit, in the digits' order. For an empty string, return an empty list.

Brute force (and an equal alternative). Start with one empty word. For each digit, replace the list of words with every word extended by every letter of that digit. There is nothing to prune — every combination is an answer — so this iterative version is just as fast as backtracking. Backtracking is shown below because it is the same template as every other problem here, and it uses only O(n) extra memory while it runs.

Key insight. Level k of the tree chooses the letter for digit k. The state is just k. When k reaches the number of digits, the path is a full word: join it and record it. Joining builds a new String, which can never change, so here the copy comes for free.

Why it is correct. Each word is one letter per digit, in order — one route down the tree. The loop at each level tries every letter of its digit, so every route is walked once.

An edge case: no digits at all. The very first line returns an empty list before any recursion starts.

Complexity. With n digits there are at most 4ⁿ words (3ⁿ when no 7s or 9s), each of length n, so time is O(n · 4ⁿ). Extra space O(n) for the path and the stack.

Input size → what is feasible: n = 8 → at most 65 536 words, instant; n = 15 → about 10⁹ words, impossible to store — then the question is usually "how many" (multiply the letter counts) or "which of them are in a dictionary" (walk a trie instead of the full tree).

Follow-ups interviewers ask. Keep only words found in a dictionary (walk a trie while building). Count the words (multiply the counts). Letter case permutations (p12-q5). All binary strings with no two 1s in a row (p12-q6).

The idea underneath: a decision tree with a fixed number of levels; maps and strings in D27 · Set & Map and D04 · Strings.

N-Queens

The task. A chess queen attacks every square in its row, its column and both of its diagonals. Place n queens on an n × n board so that no two attack each other, and return every such board. Draw each board as n strings of length n, with 'Q' for a queen and '.' for an empty square.

Brute force. Since two queens in one row attack each other, there is exactly one queen per row. Try every column for every row — nⁿ boards — and check each finished board for attacks. For n = 8 that is 16.7 million boards to find 92, and most of them were doomed after two queens.

Key insight. Place queens row by row (the state is the row r) and test each square before placing, in O(1), with three sets:

• cols holds the columns already taken.
• On a "\" diagonal (going down to the right) the value r − c is the same for every square: (0, 1), (1, 2), (2, 3) all give −1. So diag holds the r − c values already taken.
• On a "/" diagonal (going down to the left) r + c is the same: (0, 2), (1, 1), (2, 0) all give 2. So anti holds the r + c values already taken.

A square is safe exactly when its column, its r − c and its r + c are all absent. Choose = add the three values and the column; un-choose = remove them. When r == n, every row has a queen: draw the board and record it.

Why it is correct. Every valid board has one queen per row; the walk tries every safe column in row 0, then every safe column in row 1 given row 0, and so on, so it reaches every valid board. It never places an attacked queen, because each test covers all three ways a queen above could attack (rows are different by construction).

An edge case: n = 3 has no solution. Watch every attempt die in row 1 or row 2 — the result is an empty list, and the walk proves it by trying everything.

Complexity. Row r has at most n − r safe columns left (one column is used per row above), so the tree has at most n · (n − 1) · … · 1 = n! leaves, and in practice the diagonal tests cut far more. Each recorded board costs O(n²) to draw. Time O(n!) as a safe upper bound (plus O(n²) per answer); extra space O(n) for the three sets, the queen list and the stack.

Input size → what is feasible: n = 9 → 352 boards after about 72 000 square tests, instant. For larger n, counting only (p12-q22) with bit masks reaches n = 14 in well under a second; listing becomes pointless because the number of boards explodes (14 200 for n = 12).

Follow-ups interviewers ask. Count the boards only, with bit masks (p12-q22). Sudoku (p12-q20) — the same "try a value, check the row, column and box, undo" on a 9 × 9 grid. Place k non-attacking rooks or kings. Find just one board fast for large n (constructive patterns exist).

The idea underneath: backtracking with sets for O(1) checks (D27 · Set & Map); why such search problems are believed to have no fast general method in C34 · NP-Completeness; the recursion tree as a tree in Step 13.7 · Tree Problems.

Quiz

Interview questions

Variations and follow-ups of the eight problems above — the questions interviewers move to once you have solved the classic version. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow reference.

Cheat sheet

Backtracking is a depth-first walk of a tree of choices. The tree view connects it to tree traversal (Step 13.7 · Tree Problems), grid search (Step 13.9 · Graph Problems) and recursion on the call stack (D07 · Functions & the Call Stack).