Backtracking
Explore, fail fast, undo
N-Queens
Places N queens on an N×N board so none attack each other, undoing placements the moment a conflict appears.
Time O(N!) · Space O(N)
Sudoku Solver
Fills empty cells one at a time, trying digits 1–9 and backtracking whenever a digit breaks the rules.
Time O(9^m) · Space O(m)
Rat in a Maze
Finds a path from the top-left to the bottom-right of a grid, marking the route and undoing it at dead ends.
Time O(4^(N²)) · Space O(N²)
Subsets
Generates every subset of a set by, for each element, branching into taking it or leaving it out.
Time O(2^n) · Space O(n)
Permutations
Generates every ordering of a set by fixing each position in turn and swapping, then undoing the swap.
Time O(n · n!) · Space O(n)