Pruning is the win
A backtracking search is only fast because it abandons hopeless branches early. The test that prunes is the design.
Backtracking
Backtracking tries a choice, recurses, and undoes it if the choice cannot lead to a solution. It is recursion that explores options and walks back.
What you will see
6
About 3 min of reading
Try It
Explore options with backtracking.
1
All rows of length 2.
def pick(n, chosen):
if n == 0:
return [chosen]
out = []
for c in "ab":
out += pick(n - 1, chosen + c)
return out
print(pick(2, ""))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
['aa', 'ab', 'ba', 'bb']
2
Subsets of 1,2.
def subsets(a):
if not a:
return [[]]
rest = subsets(a[1:])
return rest + [[a[0]] + s for s in rest]
print(subsets([1, 2]))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
[[], [2], [1], [1, 2]]
3
Count ways to 4.
def count(n, cap):
if n > cap:
return 0
if n == cap:
return 1
return count(n + 1, cap) + count(n + 2, cap)
print(count(0, 4))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
5
4
Permutations of 1,2,3.
def perms(a):
if not a:
return [[]]
out = []
for i in range(len(a)):
rest = a[:i] + a[i + 1:]
for p in perms(rest):
out.append([a[i]] + p)
return out
print(len(perms([1, 2, 3])))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
6
Put it in order
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Data Flow
Backtracking tries a choice, recurses deeper, and abandons branches that cannot reach a solution. Pruning is what makes it finish.
1
choose an option
↓
2
recurse deeper
↓
3
hit a dead end
↓
4
undo and try the next
Line by line
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
def pick(n, chosen):
sets nothing on screen
if n == 0:
sets nothing on screen
return [chosen]
sets nothing on screen
out = []
sets nothing on screen
for c in "ab":
sets nothing on screen
out += pick(n - 1, chosen + c)
sets nothing on screen
return out
sets nothing on screen
print(pick(2, ""))
['aa', 'ab', 'ba', 'bb']
Why this works
When you have a choice
Copy versus mutate
Building new partial answers avoids undo bugs. Mutating shared state is faster but you must undo exactly.
Examples
Try and undo
def pick(n, chosen):
if n == 0:
return [chosen]
out = []
for c in "ab":
out += pick(n - 1, chosen + c)
return out
print(pick(2, ""))Each choice extends the row, then the call explores deeper. All rows come back.
Stop on a dead end
def solve(n):
if n < 0:
return 0
if n == 0:
return 1
return solve(n - 1) + solve(n - 2)
print(solve(4))A negative n returns zero, pruning that branch. The base cases end the search.
Collect solutions
def subsets(a):
if not a:
return [[]]
rest = subsets(a[1:])
return rest + [[a[0]] + s for s in rest]
print(subsets([1, 2]))Every subset either holds the head or not. Two recursive groups build them all.
Prune early
def count(n, cap):
if n > cap:
return 0
if n == cap:
return 1
return count(n + 1, cap) + count(n + 2, cap)
print(count(0, 4))Going over the cap returns zero right away. Pruning cuts whole branches.
Permutations
def perms(a):
if not a:
return [[]]
out = []
for i in range(len(a)):
rest = a[:i] + a[i + 1:]
for p in perms(rest):
out.append([a[i]] + p)
return out
print(perms([1, 2, 3]))Fix one item, permute the rest. Recursion builds every order.
Undo is implicit
def subsets(a):
if not a:
return [[]]
rest = subsets(a[1:])
return rest + [[a[0]] + s for s in rest]
print(len(subsets([1, 2, 3])))Building new lists means no shared state to undo. The undo is the copy.
Depth is choices made
def pick(n, chosen):
if n == 0:
return [chosen]
out = []
for c in "ab":
out += pick(n - 1, chosen + c)
return out
print(len(pick(3, "")))Three choices of two give eight rows. The tree of calls is the search space.
Base ends a branch
def solve(n):
if n < 0:
return 0
if n == 0:
return 1
return solve(n - 1) + solve(n - 2)
print(solve(0))The exact target returns one solution. Below it returns zero, ending dead branches.
Words this lesson uses
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← Tree traversal
Previous Lesson
Tree traversal