Algorithms · 5 lessons
Recursion & BacktrackingTry everything, but turn back early
Backtracking is disciplined brute force: make a choice, recurse, undo the choice on the way back. It is DFS over a decision tree, and it is what solves sudoku, permutations and N-queens. Pruning is what decides whether it finishes this century.
Why learn Recursion & Backtracking
Where it shows upTimetabling and seating
Give each class a slot; on a clash try the next one; if nothing fits, go back and change the previous class. That is backtracking, and N-queens is its textbook form.
→ Lesson: N-QueensEnumerating combinations
Listing every subset, permutation or combination — testing every combination of feature flags, generating every variant of a password.
→ Lesson: SubsetsSudoku and crosswords
Put a digit in a cell, back out when it breaks a rule. The way a person solves it and the way a program solves it have the same shape.
→ Lesson: Word SearchLessons
5 lessons#AlgorithmComplexityDifficultyStatus
01Subsets SubsetsTake each element or do not — 2ⁿ of themUsed for: Testing feature flag combinations, enumerating a power setO(2ⁿ·n)Space O(n)available02Permutations PermutationsA used array, or swapping in placeUsed for: Ordering a schedule, enumerating routesO(n!·n)Space O(n)available03Combinations & Combination Sum Combinations and pruningStart from an index to avoid repeats; sort first to prune earlyUsed for: Making up an amount, picking a teamExponentialSpace O(n)available04N-Queens N-queensPlace row by row, tracking attacked columns and diagonals in setsUsed for: The prototype constraint-satisfaction problem: timetabling, rosteringExponentialSpace O(n)available05Word Search Backtracking on a gridDFS across a grid, restoring the mark on the way backUsed for: Word games, enumerating maze routesO(m·n·4ᴸ)Space O(L)available