Backtracking
Try, and undo.
Some problems ask for every possible answer, or any answer that fits strict rules. Like solving a Sudoku. Backtracking tries a choice, explores where it leads, and if it hits a dead end, undoes the choice and tries the next one.

- Every possible answer
- Like solving a Sudoku
- Try, explore, undo
Every way to arrange letters
Here we build every arrangement of A, B, and C. Path holds the letters chosen so far. At each step, we try every letter not yet used. We add it, explore further with recursion, then remove it again. That removal is the backtrack. Run it. Six arrangements, three times two times one.
def arrangements(letters):
results, path = [], []
def explore():
if len(path) == len(letters):
results.append("".join(path))
return
for ch in letters:
if ch not in path:
path.append(ch)
explore()
path.pop()
explore()
return results
print(arrangements("ABC"))['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
The backtracking template
Every backtracking solution has the same skeleton. If the current path is complete, record it. Otherwise, for each possible choice, make the choice, recurse, and then undo it. Because it explores everything, it's usually exponential, like O of N factorial. So it's only practical for small inputs, or with clever pruning.
| key | value |
|---|---|
| Complete? | record the answer |
| Choose | add to the path |
| Explore | recurse |
| Undo | remove from the path |
Summary
Backtracking makes a choice, explores it, and undoes it, to try every possibility. Next, generating subsets.
Key takeaways- Choose
- Explore
- Undo