Backtracking

Build an answer one choice at a time, undo the last choice when it cannot lead anywhere, and try the next one. The tool for subsets, permutations, combinations and puzzles such as N-Queens and Sudoku.

Overview

What backtracking is

Backtracking builds an answer one choice at a time. After each choice it asks: can this partial answer still become a valid one? If yes, it goes deeper. If no, it undoes the last choice and tries the next option. When all options at a level are used up, it returns to the level above.

Every backtracking function has the same three moves, often called choose, explore, unchoose. You add a choice to the current path, call the function again to extend it, then remove the choice so the path is clean for the next option.

Path (or state) — the partial answer built so far
Choice — one option you can add at this step
Base case — the test that says the path is a complete answer
Pruning — skipping an option early because it cannot lead to a valid answer
Backtrack — undoing the last choice and returning to try another

The search tree

It helps to picture every call as a node in a tree. The root is the empty path. Each edge adds one choice. A depth-first walk of this tree is exactly the order in which the recursion runs. Nobody builds the tree in memory; only the current path from the root exists at any moment.

Here is the tree for all subsets of [1, 2, 3]. Each child only adds numbers to the right of the last one used, so no subset appears twice.

A trace on a tiny input

The code (in Code Examples below) records the path on entry, then loops from start to the end, adding one number and recursing with start = i + 1. On [1, 2, 3] the calls run in this order.

1 — 0 — [ ] — record [ ], then add 1 — 1
2 — 1 — [1] — record, then add 2 — 2
3 — 2 — [1, 2] — record, then add 3 — 3
4 — 3 — [1, 2, 3] — record; loop is empty; return and pop 3 — 4
5 — 2 — back in [1, 2] — loop done; return and pop 2 — 4
6 — 3 — [1, 3] — record; loop empty; pop 3, return, pop 1 — 5
7 — 2 — [2] — record, then add 3 — 6
8 — 3 — [2, 3] — record; pop 3, return, pop 2 — 7
9 — 3 — [3] — record; pop 3; done — 8

Notice that the path is a single list that grows and shrinks. That is why you save a copy of it (path[:] in Python) and not the list itself.

Pruning: cut branches early

Pruning is what separates backtracking from trying every possible answer and filtering at the end. You test a partial answer as soon as a choice is made, and skip whole subtrees that cannot work.

Take Combination Sum: candidates [2, 3, 6, 7], target 7, each number usable many times. Sort the candidates first. Then, once one candidate is bigger than what is left, every later one is too, so the loop can stop.

[ ] — 7 — try 2
[2] — 5 — try 2
[2, 2] — 3 — try 2
[2, 2, 2] — 1 — 2 is more than 1: stop this loop
[2, 2, 3] — 0 — answer found
[2, 2] — 3 — next is 6, more than 3: stop
[2, 3] — 2 — 3 is more than 2: stop
[2] — 5 — next is 6, more than 5: stop
[3] — 4 — try 3
[3, 3] — 1 — 3 is more than 1: stop
[3] — 4 — next is 6, more than 4: stop
[6] — 1 — 6 is more than 1: stop
[7] — 0 — answer found

The answers are [2, 2, 3] and [7]. With the sort-and-stop rule the function is called 10 times. The same code without it, which only returns once the remainder goes negative, makes 28 calls. On larger inputs the gap grows quickly.

Bound: what is left cannot work — Combination Sum stops when a candidate exceeds the remainder
Constraint check on each step — N-Queens rejects a square attacked by an earlier queen
Duplicate skip — Subsets II skips a value equal to its left neighbor at the same level
Most constrained first — Sudoku fills the empty cell with the fewest legal digits first

Three shapes to know

Most problems are one of three shapes; Combination Sum, the last row, is the combinations shape with reuse allowed. The difference is when you record an answer and where the loop starts.

Subsets — every call — index start to end, recurse with i + 1 — no — 2^n
Combinations of size k — path has k items — index start to end, recurse with i + 1 — no — C(n, k)
Permutations — path has n items — every index not yet used — no — n!
Combination Sum — remainder is 0 — index start to end, recurse with i — yes — depends on the target

Subsets and combinations use a start index, so order does not matter and [1, 2] and [2, 1] are the same answer. Permutations use a used array, because any unused number may go in any position.

Duplicate values in the input

If the input has repeats, such as [1, 2, 2], the plain code produces [1, 2] twice. The fix is to sort, then, inside one loop, skip a value equal to the value just before it. The skip applies only at the same level of the tree (i > start), so [1, 2, 2] can still use both 2s one level apart.

For permutations with repeats the rule is different: skip nums[i] when it equals nums[i - 1] and the earlier copy is not in the current path. That forces equal values to be placed in their sorted order, so each distinct arrangement appears once.

How big the search gets

Backtracking is exponential in the worst case, because the number of answers itself is exponential. Copying each answer costs up to n more.

3 — 8 — 6
10 — 1,024 — 3,628,800
15 — 32,768 — about 1.3 trillion
20 — 1,048,576 — about 2.4 quintillion

Pruning changes the real work a lot even when the worst case stays the same. For 8 queens on an 8 by 8 board, placing one queen per row in any column gives 8^8 = 16,777,216 full boards. The pruned search below makes only 2,057 calls and finds all 92 solutions.

This table is why input limits are a hint. When a problem allows n up to about 10 for permutations or about 20 for subsets, the intended answer is usually backtracking.

What you will be able to do

Recognize a problem that asks for all answers, or any answer under constraints, and pick backtracking for it.
Write the choose, explore, unchoose template for subsets, combinations and permutations from memory.
Add pruning and the duplicate skip, and explain what each one removes.
Trace the recursion on a tiny input and state the time and space cost.

When to use it

The problem asks for all subsets, combinations or permutations
The problem asks for every valid arrangement, or any one, under constraints (N-Queens, Sudoku)
Search for a path or word in a grid, where a cell cannot be reused on the same path
Split an array or string into parts that each meet a rule (palindrome partitioning, k equal-sum subsets)
Generate all valid strings or expressions (IP addresses, operators between digits)
Small input limits, such as n up to about 10 to 20, that allow exponential work

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio