pattern heroPT–23LeetCode Extension

Backtracking

Build the answer one choice at a time, and as soon as a choice leads to a dead end, undo it and try the next. Every option is covered, but branches that cannot work are cut off at once.

Variant
P20 BacktrackingSubsets · 1×

Example problem: all subsets of [1, 2, 3].

[ ]1[ ]1,212[ ]1,2,31,21,312,323[ ]path—results—
not visited yeton the way herethis stepsaved subsetfinished or undone

Find every subset of [1, 2, 3]

i = –path = –results = –
01/57
restart · back · play · step
Speed
1function explore(i):
2 if i == len(nums):
3 add copy of path to results
4 return
5 add nums[i] to path // choose
6 explore(i + 1) // with it
7 remove last from path // un-choose
8 explore(i + 1) // without it
9
10function subsets(nums):
11 path = []
12 results = []
13 explore(0)
14 return results

← → step · space play/pause

How to recognise

list every subset, permutation or combination, or place things under rules (N-Queens, Sudoku); the input is small, often n ≤ 20.

How to solve problems like this

  1. Define the state: what is chosen so far and what is left to decide.
  2. List the choices at each step. Drop the ones that break a rule.
  3. For each choice: choose it, explore deeper, then undo it.
  4. When nothing is left to decide, save a copy of the path.

Variant: Permutations

The same, but the choice is which unused number goes next. Undoing a choice frees the number for the next branch.

  1. Keep a used array next to the path: used[i] is true while nums[i] is in the path.
  2. In each call, try every index whose used is false: mark it and add the number, explore, then remove it and clear the mark.
  3. When the path holds all n numbers, save a copy.
  4. For combinations the order does not matter: pass a start index and try only from it onwards (Combinations, Combination Sum).
  5. Cut a branch as soon as a count says it cannot work: no more ")" than "(" (Generate Parentheses), one queen per row, column and diagonal (N-Queens).

Variant: Path on a grid

The same, but the path runs over a grid. Cells on the path are marked so they are not stepped on twice, and at a dead end the mark is removed so another path can use the cell.

  1. Start a search from every cell that holds the first letter.
  2. In a call: if this is the last letter, return true. Otherwise mark the cell (overwrite it with # or keep a used set).
  3. Try the four neighbours: go deeper only into one that holds the next letter. If a call below returns true, return true at once.
  4. If no neighbour works, unmark the cell and return false, so other paths can use it.
  5. With many words, search a trie of the words instead: one walk over the grid follows every word that shares the prefix so far (Word Search II).

Where it's used

  • Regular expressions. The regex engines in Python, Perl and PCRE try one way to match, and if it fails further on, they back up and try the next. That is why a badly written pattern can run for a very long time.
  • Installing packages. dnf and zypper pick package versions with a SAT solver (libsolv): it chooses a version, and on a conflict undoes the choice and tries another.
  • Prolog. A Prolog program searches with backtracking by itself: if a rule fails, the runtime goes back to the last choice and tries the next option.