Backtracking
Think of it like this
Imagine navigating a maze. At each junction, you pick a direction. If you hit a dead end, you backtrack to the last junction and try the next direction. You keep doing this until you find the exit, or exhaust all paths.
Backtracking is exactly this: explore a path until it's invalid, then undo and try another.
Maze: S → A → B → dead end
↑
S → A → C → D → exit ✓ (backtracked from B, tried C)This is different from brute force: instead of generating all possible paths and filtering, backtracking prunes paths early the moment they violate a constraint, cutting huge branches of the search tree.
The Framework: Choose → Explore → Unchoose
Every backtracking problem follows this three-step template: