March 24
Backtracking
What backtracking means, when trying a path, undoing it, and trying another is exactly what the problem needs.
What it is
Backtracking means trying one choice, seeing where it goes, and backing up when that path does not work.
It is a pattern of:
- choose
- explore
- undo
When to use it
It appears when the problem asks you to enumerate possibilities under constraints:
- combinations
- permutations
- sudoku
- valid path search
Common mistake
The classic mistake is treating backtracking as just recursion.
Recursion is often the tool.
Backtracking is the strategy of trying and undoing choices.
Better question
Before applying it, ask:
- am I exploring many possible choices?
- can I prune a path early?
- do I need to undo state when I return?
Share this page
Copy the link manually from the field below.