Brute Force, Exhaustive Search & Backtracking

the brute-force paradigm

Suppose you lost the three-digit code to a small padlock. The most stubborn, least clever thing you can do is try 000, then 001, then 002, all the way to 999 — every combination, in order, until one opens. That is brute force: solve a problem by trying all the candidate answers the problem allows and keeping the one (or ones) that work. There is no insight required, only patience and bookkeeping.

More precisely, the brute-force paradigm rests on two ingredients. First, you must be able to describe the full set of candidate solutions — all 1000 codes, all the ways to seat n guests, all subsets of a set of items. Second, you must have a cheap test that, given one candidate, says yes or no (does this code open the lock? does this seating obey everyone's requests?). Brute force then sweeps the whole candidate set, applying the test to each. If even one candidate passes, you have found a solution; if you sweep the entire set, you can also be certain when no solution exists.

The appeal is honesty and correctness: because it examines every possibility, brute force never misses an answer and never needs a clever proof to trust it. The price is time. If there are 2^n or n! candidates, the work grows explosively with the input size, so brute force is the baseline you start from and then try to beat — by being smarter about which candidates you even bother to look at. Many of the great paradigms in this domain (divide and conquer, greedy, dynamic programming, and the pruning of backtracking) are exactly the art of avoiding a full brute-force sweep.

To find the two closest of n points by brute force: try every pair (i, j) with i < j, compute the distance, and keep the smallest. There are n(n-1)/2 pairs, so the work is Theta(n^2). It is obviously correct because no pair is skipped — and a divide-and-conquer method later does the same job in O(n log n).

Brute force is the correct-by-construction baseline; cleverness is measured by how far you beat it.

Brute force being correct does not make it useless — for small inputs it is often the simplest, most reliable code you can ship, and a great reference to test a faster algorithm against.

Also called
brute-force searchexhaustive approach窮舉法蠻力法