Backtracking
Building a solution one choice at a time, undoing the last choice when it can't lead to an answer, to explore every valid combination.
Definition
Backtracking is a depth-first search over choices: choose an option, recurse to make the next choice, then undo the option and try the next one. It lists all subsets, permutations or combinations, and solves constraint puzzles like Sudoku. Pruning, which stops exploring a branch as soon as it can't succeed, is what keeps it fast enough in practice.
In practice
To list all subsets of [1, 2, 3], decide for each number whether to include it, which gives 2 x 2 x 2 = 8 subsets.
Learn it in context
Lessons that use this term.