Backtracking
Recursion: lesson 5 of 5
Choose, explore, then undo the choice and try the next.
Lesson 5 of 5 · 6 min
Backtracking
Step 1 of 11
path[ ]found0
[ ]
Backtracking builds an answer one choice at a time. The path starts empty and every option is a branch.
The Idea
Backtracking builds an answer one choice at a time. Make a choice, recurse to extend it, and when the path dead-ends, undo that choice and try the next option. The undo step is what lets a single shared list serve the entire search.
Real-World Example
Penciling in a hospital shift roster. You assign Monday, move on, and three days later hit a shift nobody can legally cover. So you erase the last pencil mark, pick a different nurse for that slot, and carry on from there.
The Code
def permute(left, path, out):
if not left: # complete: record this answer
out.append(path[:])
return
for i, x in enumerate(left):
path.append(x) # choose
permute(left[:i] + left[i + 1:], path, out)
path.pop() # un-choose
out = []
permute(["a", "b", "c"], [], out)
print(len(out), out[0]) # 6 ['a', 'b', 'c']Your turn
Put the steps in the right order.
- Undo that choice, then try the next option
- Recurse to extend the partial solution
- If the partial solution is complete, record it and return
- Add one available option to the partial solution
Mini quiz
1 / 3