Backtracking
A recursive search can build an answer one small piece at a time: a call tries each option for the next piece and calls itself to build the rest. Listing subsets works this way: a call handles the next item with two recursive calls, one that takes the item and one that leaves it out. Every sequence of those decisions ends in a subset, so no call is wasted. In many problems some choices lead to no answer, and a good search notices that as early as it can.
You get an integer . Return every string of pairs of parentheses that is balanced: each ( is closed by a later ), and each ) closes an earlier (. The strings may come in any order.
Constraints
Sample 1 ยท Input
n = 3
Output
["((()))","(()())","(())()","()(())","()()()"]
Sample 2 ยท Input
n = 1
Output
["()"]
The first sample lists the five ways to nest and line up three pairs. A string can have three of each character and still not be balanced: in ())(() the third character is a ), and the only ( before it is already closed.
The direct method writes down every string of characters and tests each one. Every position holds one of two characters, so there are strings. For that is 64 strings, of which 5 are balanced. For , the largest input, it is
strings of 16 characters, of which 1,430 are balanced (the program in the next part counts them). That is about a million characters to read, far below the rough budget of simple operations a second, so the direct method passes here. On the queens problem later on the direct method is far too slow, and this small problem shows where it wastes its work.
Half of the strings begin with ), and none of them is balanced, whatever follows. The direct method still writes out all 32,768 of them and rejects them one by one.
We can reject them all at the first character if we build the string from left to right and refuse a character as soon as it makes a balanced string impossible. We call the part written so far the prefix, and we keep two counts: opens, the number of ( so far, and closes, the number of ). Two rules decide which character may come next:
(may be added while , because a balanced string of pairs has exactly of them.)may be added while , because it has to close a(that is still open.
A prefix built by these rules can always be finished, for example by writing the ( that are still missing and then closing everything.
For the whole search fits in a picture. It starts from the empty prefix, and at every prefix it tries ( first and ) second.
( after (() and a third ( after ()(.At the start ) is refused, and with it the 8 strings that begin with ). After (( a third ( is refused, and the path goes on to (() and to the first answer, (()). The search then goes back to (, the last prefix that still has a character to try, and writes ). After () a second ) is refused, and the path goes on to ()( and to the second answer, ()().
This method is called backtracking. A backtracking search starts from an empty answer and extends it one choice at a time. When everything that follows from a choice has been tried, it goes back to the point before that choice and makes the next one.
The picture of all the choices is the search tree. Its root is the empty answer, and each arrow is one choice. Each node the search reaches is one call and holds a partial answer that breaks no rule. A path ends where its answer cannot be extended: either the answer is complete, or every next choice is refused. Backtracking follows each path to its end before it tries the next one. This order is called depth first.
Refusing a choice cuts off the whole subtree below it: no call is made for a faded prefix in the figure, or for any longer prefix that starts with it. This is called pruning.
The parentheses search in code
The search is a recursive function, visit, that receives a prefix and its two counts. A prefix of characters is an answer, and visit records it. For a shorter prefix, visit calls itself once for each character that the rules allow, with that character added to the prefix.
Each call makes exactly one decision, the next character, and which characters are allowed depends on the ones already written. The prefix records those decisions in full, but the rules need less: only how many ( and ) it holds, never where they are. So each call also receives a short summary of the earlier decisions: the two counts. With them it checks each rule in one comparison instead of counting through the prefix.
def generate_parenthesis(n):
answers = []
def visit(prefix, opens, closes):
if len(prefix) == 2 * n:
answers.append(prefix)
return
if opens < n:
visit(prefix + "(", opens + 1, closes)
if closes < opens:
visit(prefix + ")", opens, closes + 1)
visit("", 0, 0)
return answers
print(generate_parenthesis(3))
print(generate_parenthesis(1))
print(len(generate_parenthesis(8)))Prints the five strings for , () for , and 1430, the number of strings for .
Going back takes no code in this search. The expression prefix + "(" builds a new string for the call and leaves the caller's prefix as it was. When the call returns, the caller still holds its own prefix and goes on to try ).
The search finds every balanced string, because every prefix of a balanced string obeys both rules and is never refused. It finds each string only once, since two different paths spell different strings. It makes one call for each prefix it writes, the empty one included. That is 22 calls for the 5 answers of and 6,917 calls for the 1,430 answers of , so the search writes 6,917 prefixes where the direct method writes 65,536 full strings.
Worked example
The parentheses search step by step
The trace below runs the listing for and shows the prefix and its two counts at every call. It can also run , (the search in the figure) and , which has 14 balanced strings.
Prefix (empty) has open count 0 and close count 0. A close would be illegal until another open is added.
- opens
- 0
- closes
- 0
- completed
- 0
Change the example input
Current result: ["((()))","(()())","(())()","()(())","()()()"]
Permutations
The parentheses search chose between the same two characters at every step. In the next problem, which asks for every ordering of a list, the options at a step are the values that the earlier steps have not used yet.
You get an array nums of distinct integers. Return every ordering of them, in any order.
Constraints
- , where is the length of
nums - All values in
numsare different
Sample 1 ยท Input
nums = [1,2,3]
Output
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Sample 2 ยท Input
nums = [0,1]
Output
[[0,1],[1,0]]
Sample 3 ยท Input
nums = [1]
Output
[[1]]
Python's standard library lists orderings with itertools.permutations. We write the search ourselves here, because our own search can be pruned and the library call cannot, and the queens search later on needs that pruning.
An ordering is built from left to right. The first position can take any of the values in nums, the second any value except the first, and so on, down to the one value that is left for the last position.
[1, 2, 3]. The highlighted path leads to [1, 3, 2], the second ordering the search records.We build the ordering in a list called the path, because it holds the choices on the way from the root to the current node. Unlike the prefix of the parentheses search, the path is not copied for each call. Every call works on the same list: a call appends a value, calls itself, and takes the value off again.
We also need to know which values are already on the path. The array used records that: used[i] is true while nums[i] is on the path, and a call skips those values.
The permutation search in code
def permute(nums):
n = len(nums)
used = [False] * n
path, answers = [], []
def visit():
if len(path) == n:
answers.append(path[:]) # a copy: path keeps changing
return
for i in range(n):
if used[i]:
continue
used[i] = True # choose
path.append(nums[i])
visit() # explore
path.pop() # undo
used[i] = False
visit()
return answers
print(permute([1, 2, 3]))Prints the six orderings of the first sample.
The commented lines around the recursive call form a pattern that every later search repeats. A call chooses an option: it marks the value and appends it. It explores what follows from the choice, which is the recursive call. Then it undoes the choice: it takes the value off and clears the mark, so that the next turn of the loop sees the path and the marks as they were when this call began.
The undo is needed because path and used are shared by all the calls. Without the two lines after visit(), the search on [1, 2, 3] records [1, 2, 3] and nothing more: after the first ordering every value stays marked, and no call has an option left.
A finished ordering is recorded as path[:], which is a copy. The path itself keeps changing after the record is made, and it is empty when the search ends. Recording path without the copy would store the same list six times, and the first sample would come out as six empty lists.
The tree has leaves, one for each ordering: 6 for three values and for the six values this problem allows. A node just above the leaves has one value left, so it has a single child, and its level also holds nodes. One level higher, each node has two values left and two children, so the level holds nodes. One more level up, each node has three children and the level holds , and so on up to the root. Added up, the tree has fewer than nodes:
The sum in the brackets is the start of the series for , so it stays below 3. For three values the tree has nodes.
Each call loops over the positions and each ordering is copied when it is recorded, so the search takes time. The limit of six values keeps that small: 10 values already have orderings, and no search that lists every answer can be faster than writing the answers down.
Combinations
In a permutation the order matters: [1, 2, 3] and [3, 2, 1] are different answers. In the next problem an answer is a collection of values, and the order in which they are written does not matter.
You get an array candidates of distinct integers and an integer target. Return every combination of candidates that adds up to target, in any order. A candidate may be used any number of times, and two combinations count as the same when they use each candidate the same number of times.
Constraints
- , where is the length of
candidates - Fewer than 150 combinations reach the target
Sample 1 ยท Input
candidates = [2,3,6,7], target = 7
Output
[[2,2,3],[7]]
Sample 2 ยท Input
candidates = [2,3,5], target = 8
Output
[[2,2,2,2],[2,3,3],[3,5]]
Sample 3 ยท Input
candidates = [2], target = 1
Output
[]
In the first sample the two answers are and 7 by itself.
Suppose we search as we did for permutations, without the used array, since a candidate may be used again. Each call tries every candidate that is not larger than the amount still needed, and a path is recorded when nothing more is needed. On the first sample this search records
[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]The combination of two 2s and a 3 appears once for each order of its values.
To list a combination once, we allow only one of its orders: the order in which its values appear in the candidate list. After a call has chosen the candidate at position , the calls below it choose only from position onwards. Then [2, 2, 3] can be built and [2, 3, 2] cannot, because after the 3 only 3, 6 and 7 are available. No combination is lost, since the values of any combination can be put in list order, and that is the order in which the search builds it. Each call is told the first position it may choose from, its start index.
Because the calls below choose from position itself, and not from , the same candidate can be chosen again, as the problem allows. Sorting the candidates first saves some work: when a candidate is larger than the amount still needed, which the listing calls remaining, all the later ones are larger too, and the loop can end with break.
def combination_sum(candidates, target):
candidates = sorted(candidates)
path, answers = [], []
def visit(start, remaining):
if remaining == 0:
answers.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break # every later candidate is larger too
path.append(candidates[i])
visit(i, remaining - candidates[i]) # i, not i + 1: it may be reused
path.pop()
visit(0, target)
return answers
print(combination_sum([2, 3, 6, 7], 7))
print(combination_sum([2, 3, 5], 8))
print(combination_sum([2], 1))Prints the answers to the three samples.
The first sample call by call
The search makes ten calls on the first sample. Here they are in the order they are made, each with the path it was given and the amount that remains.
| Path | Remaining | What the call does |
|---|---|---|
[] | 7 | tries 2, 3, 6 and 7 |
[2] | 5 | tries 2 and 3; 6 is too large |
[2, 2] | 3 | tries 2 and 3; 6 is too large |
[2, 2, 2] | 1 | 2 is too large: a dead end |
[2, 2, 3] | 0 | recorded |
[2, 3] | 2 | 3 is too large: a dead end |
[3] | 4 | tries 3; 6 is too large |
[3, 3] | 1 | 3 is too large: a dead end |
[6] | 1 | 6 is too large: a dead end |
[7] | 0 | recorded |
Four of the ten calls are dead ends: some amount is still needed, but every candidate the call may choose is larger than that amount, and no answer begins with such a path. The parentheses search had none, because its prefixes could always be finished. At a dead end the call returns without recording anything, and its caller takes off the value it had added and tries its next candidate.
Repeated values in the input
The candidates of Combination Sum were all different. When the input holds the same value more than once, a start index is not enough to list every answer once.
You get an array nums of integers that may contain repeated values. Return every subset of it, with each distinct subset listed once, in any order.
Constraints
- , where is the length of
nums
Sample 1 ยท Input
nums = [1,2,2]
Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]
Sample 2 ยท Input
nums = [0]
Output
[[],[0]]
The array [1, 2, 2] has three positions and therefore ways to pick positions, but the sample lists 6 subsets. The subset [1, 2] can be picked with either 2, and so can [2].
One way to list subsets makes two calls per item, one that leaves the item out and one that takes it. Here we use the loop with a start index from Combination Sum instead, because then a repeated value can be skipped with one test inside the loop. A position may be used only once, so a call that chooses position passes as the next start index. Every path is a subset, so each call records its path as soon as it starts: the first call records [], the calls it makes record the subsets with one value, and so on.
Run on [1, 2, 2] as it stands, this search records [1, 2] twice and [2] twice. Each repeat comes from a call whose loop chooses the first 2 on one turn and the second 2 on the next. The call with the path [1] builds [1, 2] both ways, and the first call builds [2] both ways. Whatever a call builds after choosing the second 2, it has already built after choosing the first, because every value to the right of the second 2 is also to the right of the first.
So in the loop of one call, each value may be chosen only once, even when it appears more than once. We sort the input, which puts equal values next to each other. When a call's loop reaches nums[i], it skips it if it equals nums[i - 1], unless it is the first option the call looks at.
The listing below writes this as i > start: only an option after the first can be skipped. The option at position start is never skipped, even when it equals the value that the caller has just chosen. That is how [1, 2, 2] and [2, 2] are still built: their second 2 is chosen one level further down, by another call.
The widget draws the search tree for [1, 2, 2]. Each cell is a call, labelled with the path it records, and the two skipped values are crossed out, one under the root and one under the cell 1.
def subsets_with_dup(nums):
nums = sorted(nums)
answers, path = [], []
def visit(start):
answers.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
visit(i + 1)
path.pop()
visit(0)
return answers
print(subsets_with_dup([1, 2, 2]))Prints the six subsets of the first sample.
The search records at most subsets, 1,024 for the ten values this problem allows, and copies each one, so it takes time.
One queen per row
The queens problem is the classic example of backtracking. A chess queen attacks every square in its row, in its column and on its two diagonals, and the problem asks for the boards on which no queen attacks another.
You get an integer . Return every way to place queens on an board so that no two queens attack each other, in any order. Write each board as strings, one per row, with Q for a queen and . for an empty square.
Constraints
Sample 1 ยท Input
n = 4
Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Sample 2 ยท Input
n = 1
Output
[["Q"]]
For there are two such boards:
Take the ordinary chessboard, with . The direct method tries every way to put 8 queens on the 64 squares:
At boards a second that is 44 seconds, before the cost of testing each board.
Nearly all of those boards have two queens in one row. Two queens in a row attack each other, and there are as many queens as rows, so every row holds exactly one queen. A board is then described by the column of the queen in each row, which leaves boards. The columns must all differ as well, so the list of columns is a permutation of 0 to 7, and there are of those. We could generate them with the permutation search and keep the 92 that have no two queens on a diagonal.
Backtracking does less work still, because it never puts a queen on a square that an earlier queen attacks. The queens are placed one row at a time, from the top row down. To place the queen of a row, the search tries the squares of that row from left to right. It skips a square that an earlier queen attacks; otherwise it puts the queen there for now and recursively looks for safe squares in the rows below.
When every square of a row is attacked, the row is a dead end. The search goes back to the row above and moves that queen to its next safe square, and if that row has none left either, it goes back one row more. When the last row has its queen, the board is an answer: it is recorded, and the search goes back in the same way to look for the others.
On the board the search begins like this:
With the first queen in column 0, the second queen can go in column 2 or column 3. Column 2 leaves no square for the third queen, as on the left board: columns 0 and 2 are taken, and columns 1 and 3 are on diagonals of the second queen. Column 3 leaves one square for the third queen and then none for the fourth, as on the middle board. So no answer has its first queen in column 0, and the search knows this after placing 4 queens. With the first queen in column 1 it reaches the first answer without going back, on the right board.
Columns and diagonals
To place a queen, the search has to know whether a square is attacked. That depends on where every earlier queen stands, so the summary of earlier decisions is larger here than the two counts of the parentheses search. Rows need no test, since each row gets one queen. For the columns we keep one mark per column, as used did for the permutations. A diagonal needs a number that all of its squares share.
One step down and to the right adds 1 to the row and 1 to the column, so row - col is the same for all squares of a diagonal in that direction. One step down and to the left adds 1 to the row and takes 1 from the column, so row + col is the same for all squares of a diagonal in the other direction. Here are both numbers for every square of the board, with rows and columns numbered from 0:
row - col for each square and the right board row + col, with the column numbers underneath. The highlighted squares are the two diagonals through row 1, column 2.A queen at row 1, column 2 sets three marks: column 2, the number for its row - col and the number 3 for its row + col. A square is attacked when its column, its row - col or its row + col is marked, which takes three lookups however many queens are on the board.
The queens search in code
The function place(row) puts a queen in row and calls itself for the next row. It is the permutation search with two more kinds of marks: choosing a column marks the column and both diagonals, and undoing the choice clears the three marks. When row equals , every row has its queen, and the board is recorded.
The marks are kept in three sets: cols for the columns, diag for the values of row - col and anti for the values of row + col. The list placed holds the column chosen in each row so far.
def solve_n_queens(n):
cols, diag, anti = set(), set(), set()
placed, answers = [], []
def place(row):
if row == n:
answers.append(["." * c + "Q" + "." * (n - c - 1) for c in placed])
return
for col in range(n):
if col in cols or row - col in diag or row + col in anti:
continue # attacked
cols.add(col) # choose
diag.add(row - col)
anti.add(row + col)
placed.append(col)
place(row + 1) # explore
placed.pop() # undo
anti.remove(row + col)
diag.remove(row - col)
cols.remove(col)
place(0)
return answers
print(solve_n_queens(4))
print(len(solve_n_queens(8)))Prints the two boards for , then 92, the number of boards for .
The loop over col is the queen of this row moving from left to right. When the recursive call returns, from an answer or from a dead end, the undo takes the queen off and the loop goes on to the next safe column. When the loop ends, the call returns, which is the step back to the row above.
When a board is recorded, each column c in placed becomes one row of text: c dots, a Q, and dots up to the width .
The search on the board
On this board you make the moves of the search yourself. Click a square in the highlighted row to place a queen there; striped squares are attacked. The button "Let the search step" makes the next move of the listing: it places a queen on the next safe square of the row, or takes the last queen back when the row has none.
The counter under the buttons shows how many queens have been placed: 16 when the search on the board has finished. Listing every board with one queen per row, and no tests, would build boards. On the chessboard the listing places 2,056 queens to find all 92 answers. Listing boards instead would mean 16,777,216 with one queen per row, or 40,320 with one per column as well.
Common mistakes
Undoing only part of a choice.
- Where it breaks
- If the queens search takes the queen off
placedand leaves its three marks, it returns no boards for : the marks of abandoned queens stay, and soon every square counts as attacked. - The fix
- Undo everything the choice changed, right after the recursive call.
Skipping equal values with
i > 0in place ofi > start.- Where it breaks
- The subsets of
[1, 2, 2]come out as[[], [1], [1, 2], [2]]. The second 2 is skipped even as the first option of a call, so[1, 2, 2]and[2, 2]are missing. - The fix
- Skip only when
i > start.
Ending the loop with
breakwhen the candidates are not sorted.- Where it breaks
- The candidates
[3, 7, 2, 6]with the target 7, left unsorted, return[[7]]. After choosing 3, with 4 remaining, the loop tries 3 again, then meets 7, which is too large, and stops before it reaches the 2. - The fix
- Sort the candidates first, or use
continue.
Recall The permutation search uses a `used` array, and the searches for Combination Sum and Subsets II use a start index. Why would a start index be wrong for permutations?
A start index lets a call choose only from the position of the last choice onwards, so every path lists its values in the order of the input. That builds [1, 2, 3] and never [3, 2, 1]. A permutation search has to build every order, so each call looks at all positions and skips only those that are marked as used.
Further reading
- Jeff Erickson (PDF)Algorithms, Chapter 2: Backtracking(opens in a new tab)
The row-by-row queens search and its recursion tree, game trees, subset sum, and the general pattern of one decision per call. Parts of this page adapt this chapterโs text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- USACO Guide, BronzeComplete Search with Recursion(opens in a new tab)
Subsets and permutations by recursion, then CSES Chessboard and Queens solved twice: by checking all permutations and by backtracking, with a practice list.
- Antti Laaksonen, free PDFCompetitive Programmerโs Handbook, chapter 5(opens in a new tab)
Section 5.3 is backtracking on the queens problem. Section 5.4 prunes a search for grid paths in four steps and measures each one: from 76 billion recursive calls down to 69 million.
- OI Wiki, in Chineseๅๆบฏๆณ(opens in a new tab)
A short statement of the method, worked on USACOโs Checker Challenge, a queens problem solved with one array per column and per diagonal direction, as in this lesson.
- WikipediaCatalan number(opens in a new tab)
The number of balanced strings of pairs, 5 for and 1,430 for , is the th Catalan number. The article derives the formula in several ways.
- WikipediaEight queens puzzle(opens in a new tab)
The 92 solutions and the 12 that remain when rotations and reflections are counted once, the number of solutions for larger boards, and other ways to search.