Backtracking

Choose, Explore, Undo

1:00

A systematic depth-first search over a decision tree that prunes dead branches early and undoes each choice on the way back — the engine behind N-Queens, permutations, subsets, and Sudoku.

By the end, you can

Explain what backtracking is and how it differs from brute force, greedy, and dynamic programming.
Trace a backtracking search on a small decision tree, identifying where pruning cuts subtrees.
Write the universal backtracking template (is_complete / options / is_valid / choose / recurse / unchoose) and explain why each line is necessary.
Apply the choose-explore-unchoose pattern to N-Queens, and identify the column/diagonal conflict checks.
State the worst-case time complexity O(b^d) and space complexity O(d), and give the specific complexities for subsets (2^n) and permutations / N-Queens (n!).
Decide when to reach for backtracking versus dynamic programming based on whether subproblems overlap.

Up next in Algorithms & Graph Algorithms