The most honest algorithm in the world
Suppose you have lost the three-digit code to a small padlock. The least clever thing you can possibly do is try 000, then 001, then 002, all the way to 999, until one opens. No insight, no shortcut — just patience and bookkeeping. That is the brute-force idea in one picture: to solve a problem, try every candidate answer the problem allows and keep the one (or ones) that work. We are starting this whole rung here on purpose, because brute force is the floor everything else stands on — the baseline you measure cleverness against.
Why open with the dumb method? Because it has one priceless virtue: it is obviously correct, and it is correct for a reason you can state in one breath. We spent the earlier rungs learning to separate the problem from the algorithm and to ask which case a running time refers to. Brute force is where those habits first pay off. It will be too slow for big inputs — that is the whole drama of this rung — but it is the one method you never doubt, and that makes it the perfect place to learn what "trying everything" really demands.
Two halves: a generator and a tester
Look closely at the padlock sweep and you will see two distinct jobs alternating. One job produces the next thing to try (000, then 001, ...); the other job checks it (does the lock open?). Pull those apart and you have the engine inside almost every brute-force method: generate-and-test. The generator is a procedure that hands you candidate solutions one at a time; the tester is a predicate that takes one candidate and answers yes or no — does this candidate satisfy the problem's requirements?
while generator has more candidates:
x = generator.next() # generate
if test(x): # test
report x # (or stop here for the first hit)Keeping the two halves separate is a genuine design win, not just tidiness. You can swap in a smarter generator — one that produces fewer doomed candidates — without touching the test, and you can sharpen the test without rewriting the generator. The total cost of the loop is easy to read off this split: it is roughly (number of candidates generated) times (cost of one test). That product is the number we will spend the rest of the rung attacking, almost always by shrinking the first factor.
Why it is always right: complete enumeration
The correctness of brute force rests on one disciplined promise about the generator, called complete enumeration: list every candidate, once each, leaving none out and repeating none. Two conditions must both hold. No omission means every candidate the problem allows really does appear in the sweep — this is what lets you trust a "no" answer, because you can only declare "no solution exists" if you genuinely looked at all of them. No duplication means each candidate appears at most once — this is what keeps counts honest and stops you wasting work.
How does a generator guarantee both at once? The standard move is to impose an order on the candidates and walk it from first to last. Number the padlock codes 0 to 999 and count upward: numeric order visits each exactly once, so by a tiny induction nothing is skipped and nothing repeats. The same idea scales up. To list the subsets of n items, count integers 0 to 2^n - 1 and read each as a bitmask (enumerating subsets); to list the orderings of n items, use lexicographic order (enumerating permutations). In every case, a fixed order is what turns "try everything" from a hopeful wish into a procedure you can prove visits everything.
Counting the cost: how big is the haystack?
Before you search for the needle, you should know how big the haystack is. The set of all candidates is the search space — every place the real answer could possibly hide. Its size is what decides whether brute force is an option at all, and the bad news is that it usually explodes with the input. Choosing yes/no for each of n items gives 2^n candidates (the powerset). Arranging n items gives n! orderings. Assigning one of k labels to each of n items gives k^n. These counts are not incidental — they are exactly why pure brute force is exponential.
Put numbers on it to feel the cliff. Generating one subset costs about n work (to read its bits), so sweeping all subsets is Theta(n * 2^n): comfortable for n up to about 20-25, hopeless past 30. Permutations are even crueler — n! outgrows every 2^n, so n = 13 already passes six billion orderings and n = 20 is utterly out of reach. This is the honest verdict the earlier rungs taught us to read: exponential growth is not "slow," it is a wall. A method that is unbeatable at n = 10 can be physically impossible at n = 60.
Pure generate-and-test is blind — and that is the opening
Here is the flaw worth obsessing over. In pure generate-and-test the generator is blind: it produces candidates with no regard for the tester, so it cheerfully churns out vast numbers of obviously-doomed ones. Trying to seat eight dinner guests with conflicting demands, a blind generator will build a complete seating of all eight before noticing that guests one and two — fixed in the very first two chairs — were never allowed to sit together. It finished an entire arrangement to discover a contradiction that was visible after two decisions.
The single most powerful improvement is to push knowledge from the tester back into the generator: refuse to generate any candidate that is already known to fail. When that feedback happens partway through building a candidate — the moment the first two chairs already break a rule, abandon every completion of them at once — pure generation becomes backtracking, and the savings can be enormous. This is the hinge of the whole rung: we are not throwing brute force away, we are teaching its generator to stop wasting time. The early rejection itself has a name we will lean on, feasibility pruning.
From here the rung climbs in clear steps. Guide 3, Backtracking, makes the make-recurse-undo loop precise and shows it as a depth-first walk of a tree of partial solutions, with N-queens and subset-sum as the worked templates. Guide 4, Branch and Bound, upgrades pruning for optimization — cut a subtree whose best possible outcome cannot beat the best answer found so far. Guide 5, Meet in the Middle, attacks the exponent itself, often turning 2^n into roughly 2^(n/2). Every one of them is the same move: start from this honest, correct baseline, then refuse to look at candidates that cannot matter.