Recap: Backtracking

Choose, explore, unchoose; copy at the leaf; count the leaves; prune early.

Backtracking builds solutions one choice at a time on one shared path, undoing each choice before the next, and prunes the branches that already break a rule. This card gathers what the topic established and where each idea was taught.

What the topic established, and which card it was on
The idea	Where
Choose, explore and unchoose walk a tree of partial solutions with one shared path	Backtracking: Choose, Explore, Unchoose
A permutation search fills one position per level, and each unchoose shortens the path by one	Trace Every Ordering of Three Items
Without the undo, later branches inherit earlier choices and the output is wrong without any error	Forgetting to Undo the Choice
Record a copy of the path at a leaf; recording the path itself leaves every entry empty	Backtracking in Python, Java and TypeScript
Listing everything costs leaves × copy: O(n · 2ⁿ) for subsets and O(n · n!) for permutations	Costing a Backtracking Search by Counting Its Leaves
Checking each rule on the partial solution prunes whole subtrees: 2,056 queens placed against 19,173,960 on 8 × 8	Pruning a Branch as Soon as It Breaks a Rule
Sorted costs let one total over the budget prune every later choice at a node	Backtracking Example: Choosing Dishes That Fit a Budget Exactly
Pruning the seating search builds 8 complete seatings instead of 24	Practice: Seating Guests Who Refuse to Sit Together

Backtracking on n items

Subsets: 2ⁿ leaves, O(n · 2ⁿ) to list
Permutations: n! leaves, O(n · n!) to list
Extra space: O(n); the path, the flags and the call stack, not counting the output
Pruning: Skips whole subtrees; worst case still exponential; helps when most leaves fail

Backtracking tries every choice and keeps none of them for good. Greedy Algorithms, the next topic, makes the opposite bet: one choice per step, never undone.

← → move through sections and cards