Backtracking is a problem-solving algorithmic technique that builds candidates for a solution incrementally. If at any point it realizes that a partial candidate cannot possibly lead to a valid solution, the algorithm abandons it ("backtracks") and immediately tries another path to avoid wasting time.
- Decision Problems: Find any one valid path to see if a solution is even possible.
- Optimization Problems: Search all paths to find the absolute best or most efficient solution.
- Enumeration Problems: Hunt down and list every single valid solution that exists.