NOTE
Backtracking
Search a decision tree by choose–recurse–undo, with pruning and state management.
This is a historical learning note and may contain outdated or incomplete understanding.
Backtracking enumerates candidates through a decision tree: make a choice, recurse, then undo the choice before trying the next alternative.
The generic pattern is useful for permutations, combinations, subsets, constraint puzzles, and path construction.
Performance depends on pruning: reject partial states that cannot lead to a valid/better solution. Carefully define which state is shared/mutated so the undo step fully restores the previous branch.