Counting before computing
The previous guide gave you generate-and-test as the honest baseline: produce every candidate, check each one, keep the good ones. But a baseline is only useful if you know what it costs, and the cost of trying everything is governed by one number — how many candidates there are. That set of all candidates is the search space, and the single most important habit in this whole rung is to estimate its size before you write a line of code. A method that is obviously correct can still be obviously hopeless, and the size of the search space is what tells you which.
Here is the reflex to build. When you read a problem, ask: "what shape is a single candidate?" Is it a yes/no choice for each of n items? An ordering of n things? A way to pick k items out of n? Each shape has a known count, and that count, written as a function of the input size n, is the running time of brute force up to the per-candidate test cost. Counting candidates is therefore not a side calculation — it is the analysis. Everything else in this rung is a trick for not having to visit all of them.
The three classic shapes and their sizes
Most brute-force problems wear one of three costumes. The first is subsets: for each of n items you make an independent in-or-out choice, so enumerating all subsets means walking through 2 times 2 times ... times 2, which is 2^n possibilities (including the empty set and the full set). The clean way to picture this is a length-n binary string, one bit per item: every such string names exactly one subset, and there are 2^n strings. Subset-sum, choosing which items to pack, turning switches on or off — all of these are the 2^n costume.
The second costume is orderings, also called arrangements. Enumerating all permutations of n distinct things gives n! of them, because there are n choices for what goes first, then n-1 for second, then n-2, all the way down: n times (n-1) times ... times 1. Routing a salesman through n cities, seating n guests, scheduling n jobs in some order — these are the n! costume. The third is choosing k of n without order, the combinations, of which there are "n choose k" = n! / (k! (n-k)!); selecting a committee of k people from n, or which k edges to delete, lives here.
shape count n=10 n=20 n=60 -------------------------------------------------------------- subsets 2^n 1,024 ~1.0 million ~1.2e18 permutations n! ~3.6 mil ~2.4e18 ~8.3e81 combos n/2 n choose n/2 252 184,756 ~1.2e17
Why 2^n and n! are different kinds of doomed
It is tempting to lump 2^n and n! together as "too big," but they fail at very different speeds, and seeing the gap sharpens your judgment. Both are part of the exponential side of the growth hierarchy — both eventually crush any polynomial like n^2 or n^100 — but n! grows faster than 2^n for every n beyond a tiny start. A clean way to feel it: 2^n multiplies by a fixed factor of 2 each time n increases by one, while n! multiplies by n, an ever-growing factor. So the gap between them is itself widening without bound.
Stirling's approximation makes it precise: n! is roughly (n/e)^n times a slowly-growing tail, so taking logarithms, log(n!) is about n log n while log(2^n) is just n. That extra log n factor in the exponent is the whole story. Practically, it means an algorithm that enumerates subsets can sometimes be rescued by a better machine or a cleverer constant; an algorithm that enumerates permutations almost never can, because the wall arrives at n around 12. Knowing which exponential you are facing tells you whether optimization is even worth attempting.
Sizing a real problem, step by step
Let us size the search space of a concrete problem you will meet again in this rung: placing n non-attacking queens on an n-by-n board, the n-queens problem. The point is to see how a naive count and a smarter count can differ by a galaxy, even before any backtracking prunes a single branch. The trick is always the same: pin down exactly what a candidate is, then multiply the choices.
- Most naive: a candidate is any placement of n queens among the n^2 squares, choosing n squares out of n^2. That is 'n^2 choose n'. For an 8x8 board that is '64 choose 8', about 4.4 billion candidates — already painful.
- One observation shrinks it hugely: at most one queen per column. So a candidate is a choice of row (1..n) for each of the n columns — n choices per column, n columns, giving n^n. For n = 8 that is 8^8 = about 16.7 million. We cut billions to millions just by encoding the candidate better.
- A second observation: no two queens share a row either, so the row-assignment must be a permutation of 1..n. Now the count is n!, which for n = 8 is just 40,320 — three orders of magnitude below the n^n count, and five below the naive one.
- We have not run any algorithm yet — we only changed how we describe a candidate. The lesson is that the search space is not fixed by the problem; it is fixed by your representation, and a smarter representation is the cheapest speedup there is.
And we still have not pruned. Backtracking — the subject of the next guide — will refuse to even extend a partial placement the moment two queens threaten each other, lopping off whole subtrees of that n! space. But notice the ordering of ideas: first you encode the candidate well to make the space as small as honest counting allows, then you prune what remains. Sizing comes first because it tells you whether pruning could possibly be enough.
When the space is too big: splitting it in half
Sometimes the search space is genuinely 2^n and pruning does not help because every candidate really must be considered — for example, counting how many subsets of n numbers sum to a target when the numbers are arbitrary. Here a beautiful idea, previewed now and detailed at the end of this rung, comes from cutting the count's arithmetic in half rather than the search itself: meet in the middle. Split the n items into two halves of size n/2, enumerate each half separately, then combine.
The arithmetic is the whole point. Two halves of size n/2 each have only 2^(n/2) subsets, so you generate 2 times 2^(n/2) candidates instead of 2^n. Since 2^(n/2) is the square root of 2^n, you have turned, say, 2^40 (a trillion, hopeless) into about 2^20 (a million, easy) per half. You pay for it in memory — you must store one half's results to match against the other — and in a sorting or hashing step to do the matching. It does not beat the exponential, but it halves the exponent, which is often the difference between feasible and not.
Step back and see the map of this whole rung as a response to one question: the search space is some size, now what? If it is small, enumerate it all and relax — clarity beats cleverness. If it is large but structured, backtrack to skip dead branches, and bound the search to skip hopeless ones. If it is large, unstructured, but splittable, meet in the middle to take its square root. In every case the first move is the same one this guide is about: count the candidates, because you cannot tame a space whose size you have not measured.