Backtracking Foundations
7 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.
Recursion in One Page
A function is a named chunk of code. You write it once with def, then run it by calling its name. Recursion is a function that calls itself. To stop it running forever, every recursive function has two parts. The base case is a situation so small that the function finishes right away, with no further call. The recursive case does one small piece of work, then calls itself on a smaller problem. Take count_down. Calling count_down(3) prints 3 and calls count_down(2). That prints 2 and calls count_down(1). That prints 1 and calls count_down(0). Now n is 0, the base case: it prints go! and returns. Here is the surprise. When a call returns, the call that was waiting carries on with the line right after its call. So count_down(1) prints back from 1, then count_down(2) prints back from 2, then count_down(3) prints back from 3. Each call has its own private n, so the three calls never mix up their numbers.
The intuition
You never need to follow every call in your head. Do one small piece of work, and trust the smaller call to do the rest. Only two things need checking: does each call make the problem smaller, and is there a base case that stops it. The calls that are waiting form a pile called the call stack, like plates in a canteen. The newest call sits on top and is the only one working. When it finishes, it is lifted off, and the plate under it carries on exactly where it paused. That moment, carrying on after the smaller call comes back, is the one thing to remember, because backtracking uses it.
- A recursive function calls itself on a smaller problem.
- The base case is where it stops. Without one, the calls never end.
- Every call has its own private copy of its inputs, such as n.
- Waiting calls form a pile called the call stack. Only the top one is working.
- When a call returns, the call below it carries on with the line right after the call.
A real-world analogy
A pile of plates in a canteen. Each waiting call is one plate. The plate on top is the call that is working right now. Calling a smaller problem puts a new plate on top. Finishing a call lifts its plate off, and the plate underneath becomes the top one again, with its own n still written on it. The bottom plate is the first call you made, and it is the last one to be lifted off.
def count_down(n): # one input, n
if n == 0: # base case: nothing smaller to do
print('go!')
return # stop here, make no more calls
print(n) # one small piece of work
count_down(n - 1) # recursive case: a smaller problem
print('back from', n) # runs AFTER the smaller call comes back
count_down(3) # prints 3 2 1 go! back from 1 back from 2 back from 3One Choice at a Time: The Decision Tree
Some problems ask for every way to arrange something. Our running task: you have 2 pairs of round brackets, so 4 brackets in total. List every valid string. A string is valid when every opening bracket ( is closed later by a ), in the right order. (()) and ()() are valid. ())( is not valid. The method is to build each string one bracket at a time. At each of the 4 positions there are 2 choices, ( or ). That makes 2 x 2 x 2 x 2 = 16 strings. Draw it as a decision tree. The top is the empty string. Each branch adds one bracket. After 4 branches we reach a leaf, which is a finished string. The string built so far is called the path. In the code, build adds ( and calls itself, then adds ) and calls itself. The + sign glues text together, so path + '(' makes a NEW string and leaves path unchanged. The list out is a row of boxes that starts empty. out.append(x) puts x in a new box at the end, and len(out) counts the boxes.
The intuition
The tree turns one big question, which of all the arrangements are valid, into a tiny question asked again and again: what is the next bracket? Every finished string is exactly one path from the top to a leaf, so no string is missed and no string appears twice. You never draw the tree in memory. The recursive calls simply walk through it, and the pile of waiting calls always holds the path to the spot you are standing on.
- Build the answer one choice at a time. Here a choice is one bracket.
- The path is everything chosen so far. The empty path is where you start.
- A leaf is a finished path. Each full path from the top to a leaf is one possible answer.
- With 2 choices at each of 4 positions there are 2 x 2 x 2 x 2 = 16 leaves.
- A string is valid if a tally (( adds 1, ) subtracts 1) never goes below 0 and ends at 0.
A real-world analogy
A shelf with 4 empty boxes in a row. You put a red sticker or a blue sticker in each box, left to right. The first box has 2 choices, then the second box has 2, and so on, giving 16 patterns. The row of stickers so far is the path. A box with all four stickers is a leaf. Red stands for ( and blue for ). The question of which patterns are valid comes after the patterns exist.
def build(path, length, out): # path = brackets chosen so far
if len(path) == length: # a leaf: the string is finished
out.append(path) # save it at the end of the list out
return
build(path + '(', length, out) # choice 1: add an opening bracket
build(path + ')', length, out) # choice 2: add a closing bracket
out = [] # an empty list
build('', 4, out) # start from the empty string, length 4
print(len(out)) # 16
print(out) # all 16 strings, in tree orderChoose, Explore, Unchoose
Gluing a new string at every call works. The other style, used in most backtracking code, keeps ONE list called path and edits it. A list is a row of boxes. path.append(x) puts x in a new box at the end. path.pop() takes the last box off. Both only touch the end, so both are quick. Our running example: a lock takes a code of 2 digits, and each digit is 1 or 2. Listing the codes follows three moves for each option d: choose it with path.append(d), explore by calling the function to fill the remaining digits, then unchoose it with path.pop(). A for loop can walk over a list written in square brackets: d is 1, then 2. Why unchoose? There is only one path list, shared by every call. When the explore call comes back, the list still holds d. Without the pop, the next option would be added on top of it, and the code [1, 2] would come out as [1, 1, 2]. The pop puts the list back exactly as it was before the choice, so the next option starts from the same place.
The intuition
Remember how a call that returns lets the waiting call carry on with its next line? The pop sits on that next line. So the order is: choose, then everything the smaller call does, then undo. When the smaller call has finished, the list looks exactly as it did before the choose, which is what lets the loop try the next option as if the first had never happened. That undo is the whole idea of backtracking: step forward, explore, step back.
- Keep one list called path and share it with every call.
- Choose is path.append(option). Explore is the recursive call. Unchoose is path.pop().
- The pop goes AFTER the recursive call comes back, never before it.
- Every append needs a matching pop. After a full loop the path is exactly what it was at the start.
- Without the pop, old choices stay in the list and pile up in later answers.
A real-world analogy
A hiker in a maze unrolls a ball of thread. Each junction chosen means more thread laid down. That thread is the path. At a dead end, or after the last branch, the hiker winds the thread back to the junction and tries the next corridor. Laying thread is append, exploring the corridor is the call, and winding the thread back is pop. Without winding it back, the thread would still run down the old corridor, and every new route would start with a tangle.
def pick(path):
if len(path) == 2: # a 2-digit code is finished
print(path)
return
for d in [1, 2]: # d is 1, then 2
path.append(d) # choose: add d at the end
pick(path) # explore: fill the remaining digits
path.pop() # unchoose: remove d again
pick([]) # start with an empty pathRecording a Finished Answer
Every call has a path of some length. The base case is the moment the path is finished. For 1 pair of brackets that is len(path) == 2. The base case does two things: it saves the answer, then it returns so the call stops. Saving needs care. If you write out.append(path), you do not save the brackets. You save a second name for the same list. Later pops empty that list, and every saved name shows the change. With 4 finished strings you would end with [[], [], [], []], four names for one empty list. The fix is to save a copy. For brackets we glue the pieces into text with ''.join(path): the two quotes with nothing between them mean nothing is put between the pieces, so ['(', ')'] becomes '()'. Text never changes afterwards, so it is a safe snapshot. For a list of numbers, path[:] makes a copy: a slice takes part of a list, and [:] takes from the start to the end, as a new list. The loop for ch in '()' walks over a string one character at a time.
The intuition
The path is a whiteboard that gets wiped and rewritten again and again. The answer must survive the wiping. Saving the whiteboard itself saves nothing, because it will be wiped. Saving a snapshot of what is written right now keeps it for good. So the one rule is: when you save, save a copy. The unchoose is free to wipe the path as often as it likes, because the copies are already safe in the answers list.
- The base case has two jobs: save the finished answer, then return.
- out.append(path) saves the live list, not a snapshot. Later pops change what it shows.
- Save a copy instead: ''.join(path) for a list of text pieces, or path[:] for any list.
- Without the return, the call would carry on and try to extend a finished path.
- Text cannot be changed after it is made, so a joined string is safe to keep.
A real-world analogy
A whiteboard and a photo album. The whiteboard is path, wiped between attempts. The album is out. If you could glue the whiteboard itself into the album, then every page would show whatever is on the board right now, which at the end is a blank board. Taking a photo of the board each time you finish a drawing puts a lasting picture on a page. The photo is the copy.
def build(path, out):
if len(path) == 2: # 1 pair = 2 brackets: finished
out.append(''.join(path)) # save a COPY, glued into text
return # then stop
for ch in '()': # ch is '(' then ')'
path.append(ch) # choose
build(path, out) # explore
path.pop() # unchoose
out = []
build([], out)
print(out) # ['((', '()', ')(', '))']Pruning: Skip Choices That Cannot Work
In the tree of 16 strings, most branches are doomed early. A prefix is the first few brackets of a string. Take the prefix ')': the tally is already -1, and adding more brackets can never undo that. Pruning means asking, before each choice, whether it can still lead to an answer. If not, you skip it, and the whole branch below it is never visited. For n pairs, two rules decide. Rule 1: add ( only while opens < n, where opens counts the ( used so far. Rule 2: add ) only while closes < opens, where closes counts the ) used so far. That means a ) is allowed only when some ( is still waiting to be closed. The counters opens and closes are passed into each call, and each call gets its own copy, as in the recap. The two ifs are separate, because sometimes both choices are allowed.
The intuition
The rules never let a branch go wrong, so no check is needed at the end. When the path reaches length 2n, the counters satisfy opens <= n and closes <= opens, and opens + closes = 2n. The only way is opens = n and closes = n. And since a ) was only added when it had a ( to close, the tally never went below 0. Every finished string is valid, and pruning has not lost any valid string, because each valid string follows these rules at every step.
- Pruning means skipping a choice that cannot lead to an answer, so its whole branch is never visited.
- Rule 1: add ( only while opens < n.
- Rule 2: add ) only while closes < opens.
- Use two separate ifs, not if and else: sometimes both choices are allowed.
- With both rules, every string that reaches length 2n is valid, so no final check is needed.
A real-world analogy
Driving through a town with road-closed signs. A sign at the start of a street tells you the street leads nowhere, so you do not drive down it to find out. All the side streets beyond it are skipped as well. The signs are the two rules. The earlier a sign sits, the more roads you never visit. Checking at the very end would be like driving every street and only then asking whether it was open.
def gen(path, opens, closes, n):
if len(path) == 2 * n: # finished: n opens and n closes
print(''.join(path))
return
if opens < n: # rule 1: some opens are left to use
path.append('(') # choose
gen(path, opens + 1, closes, n) # explore
path.pop() # unchoose
if closes < opens: # rule 2: an open is waiting for its close
path.append(')')
gen(path, opens, closes + 1, n)
path.pop()
gen([], 0, 0, 2) # prints (()) and ()()Counting the Work
How much work is backtracking? Count the calls, since each call is one box in the tree. For 2 pairs, the pruned tree has 8 calls. For 3 pairs it has 22 calls, against 127 for the full tree (1 + 2 + 4 + 8 + 16 + 32 + 64). Now count the finished strings. The pruned search finds exactly the valid ones: 1, 2, 5, 14, 42, 132 for n = 1 to 6. The build-everything-then-check approach, called brute force, has 4, 16, 64, 256, 1024, 4096: that is 4 ** n, where ** means 'to the power'. In the code, range(1, 7) counts 1, 2, up to 6, and stops before 7. A function can hand back a number with return, and the caller can add it up. In the code, return 1 means 'I am one finished string', and each call adds what its children hand back. The brute-force count multiplies by exactly 4 for every extra pair. The valid count multiplies by 2, then 2.5, 2.8, 3 and 3.14, creeping toward 4.
The intuition
Big-O is a short way to say how the number of steps grows as the input grows. Finding the biggest item in a row of n takes about n steps, written O(n): double the row, double the steps. Here the steps get multiplied by roughly 4 for each extra pair, which is called exponential growth, about O(4^n) (the exact count is a little smaller). That sounds scary, but the job is to list every answer. With 132 answers you must write 132 strings, so no method can do less work than the number of answers. Pruning guarantees no call is wasted on a string that fails. Space is small: the pile holds at most 2n + 1 plates, which is 7 for n = 3.
- Count work by counting calls: each call is one box in the tree.
- The pruned tree for n = 3 has 22 calls. The full tree has 127.
- The number of valid strings for n = 1 to 6 is 1, 2, 5, 14, 42, 132.
- Time grows exponentially, roughly 4 times more for each extra pair. That is fine when the output itself is that large.
- Space is small: the pile holds at most 2n + 1 calls, plus the path of at most 2n boxes.
A real-world analogy
A chain letter. Every person who gets it sends it to 2 friends. After 1 round 2 people have it, after 2 rounds 4, after 3 rounds 8, and so on: the count doubles each time. That is exponential growth. Each round is one more level of the tree, and each person is a call. If some people refuse to forward the letter, those branches stop. That refusal is pruning, and the whole letter shrinks, but it still grows round by round.
def count(opens, closes, n): # how many ways can this path be finished?
if opens + closes == 2 * n: # finished: that is one string
return 1
total = 0
if opens < n: # rule 1
total += count(opens + 1, closes, n)
if closes < opens: # rule 2
total += count(opens, closes + 1, n)
return total # hand the sum back to the caller
for n in range(1, 7): # n = 1, 2, ... 6
print(n, count(0, 0, n), 4 ** n) # n, valid strings, all stringsThe Template and How to Spot a Backtracking Problem
Every backtracking solution has the same six pieces. First, is the path finished? Second, if so, record a copy. Third, return. Then, for each allowed choice: fourth, choose it (append). Fifth, explore it (call yourself). Sixth, unchoose it (pop). Only the choices and the finished test change from problem to problem. Here is a new problem with the same shape: a shelf holds books A, B and C, and you take 2 of them, in any order. The answers are AB, AC and BC. To avoid listing AB and BA as different, each call may only take books after the one it just took. range(start, len(books)) counts start, start + 1, up to len(books) - 1. For example, range(1, 3) gives 1, 2. And books[i] reads the book in box number i, counting from 0. The brackets code from the last concepts has the very same pieces. Its allowed choices are two ifs instead of a for loop.
The intuition
Spot the pattern from the question. If it asks for ALL the combinations (groups where the order does not matter), ALL the orders (permutations), ALL the subsets (every smaller group you can pick), or every valid arrangement, the answers are built from a series of choices, each choice shrinks what is left, and some choices are against the rules. That is backtracking. If the question wants only one number, such as the biggest total, you do not usually need to list every possibility. Once you know it is backtracking, ask three questions: what is one choice, when is the path finished, and which choices are not allowed.
- The six pieces: finished?, record a copy, return, choose, explore, unchoose.
- Only three things change from problem to problem: what a choice is, when the path is finished, and which choices are allowed.
- In the brackets code the allowed choices are two ifs. In the books code they are a for loop over range(start, len(books)).
- Backtracking suits questions that ask for all combinations, orders, subsets or valid arrangements.
- Always record a copy of the path, never the path itself.
A real-world analogy
A recipe card. The method printed on the card is always the same: prepare, cook, taste, clean up. What changes from dish to dish are the ingredients and the oven time. The template is the printed method. The choices, the finished test, and the allowed rules are the ingredients and the oven time. A cook who knows the card can make a new dish by changing only those three lines.
books = ['A', 'B', 'C']
def pick(start, path, out):
if len(path) == 2: # 1. finished?
out.append(path[:]) # 2. record a COPY
return # 3. stop
for i in range(start, len(books)): # each allowed choice
path.append(books[i]) # 4. choose
pick(i + 1, path, out) # 5. explore (only later books)
path.pop() # 6. unchoose
out = []
pick(0, [], out)
print(out) # [['A', 'B'], ['A', 'C'], ['B', 'C']]