Recursion and backtracking

Backtracking is a way to search through all possible solutions by building one step at a time and undoing a step as soon as it leads to a dead end. Think of solving a maze by always taking a path, and when you hit a wall, walking back to the last junction and trying the next branch. In code it’s a recursive function that makes a choice, recurses, then reverses that choice. The key to making it practical is pruning: checking early whether a partial solution can still work, so you skip whole branches. Puzzles like N-Queens and Sudoku, generating permutations or subsets, and constraint solvers all use it.