Backtracking and constraint search
Backtracking explores a decision tree depth-first, abandoning a branch the moment it cannot lead to a valid solution. The undo step — restoring state after exploring a choice — is what separates it from plain recursion.
Pruning is where the performance comes from. N-Queens, Sudoku, and permutation problems are all exponential in the worst case, but a good validity check discards enormous subtrees before they are ever expanded.
Time and space complexity
| Problem | Time | Space | Notes |
|---|---|---|---|
| Subsets | O(2ⁿ × n) | O(n) | Every element in or out |
| Permutations | O(n! × n) | O(n) | All orderings |
| Combinations (n choose k) | O(C(n,k) × k) | O(k) | Pruned by index |
| N-Queens | O(n!) | O(n²) | Heavily pruned in practice |
| Sudoku solver | O(9^cells) | O(1) | Constraint propagation prunes hard |
How to use this visualizer
Pick a backtracking problem to load its decision tree.
Step forward and watch each choice push deeper into the tree.
Watch a constraint fail and the algorithm undo that choice.
Note the pruned subtrees that are never explored.
Frequently asked questions
Brute force generates every candidate and tests each at the end. Backtracking tests partial candidates as it builds them and abandons a branch as soon as it becomes invalid, so entire subtrees are never generated. Both are exponential in the worst case, but backtracking is dramatically faster whenever constraints prune early.
Three steps inside a recursive function: if the current state is a complete solution, record it and return; otherwise, for each candidate choice, apply the choice, recurse, then undo the choice. That final undo — restoring the state you mutated — is the "backtrack" and is the step most often forgotten.
Sort the input first, then within each recursion level skip a candidate if it equals the previous one and that previous one was not itself chosen at this level. This ensures duplicates are only ever used in one canonical order, which removes repeated subsets and permutations without a post-hoc deduplication pass.