Brute force — exhaustive search, when acceptable: Worked examples

The scenario matrix

Every brute-force problem lives in exactly one search-space shape, and each shape has a size formula (all derived in the parent note). The matrix below lists every case class this topic can throw, and which worked example nails it.

Cell	Search-space shape	Size formula	Danger case to cover	Example
A	Unordered pairs	$(2 n) = \frac{n ( n - 1 )}{2}$	double-counting $(i, j)$ vs $(j, i)$	Ex 1
B	All subsets	$2^{n}$	$n = 0$ → the empty set case	Ex 2
C	All permutations	$n!$	is $n$ small enough?	Ex 3
D	$k$ -tuples over alphabet $b$	$b^{k}$	short code = weak	Ex 4
E	Feasibility limit (too slow?)	plug into $≲ 1 0^{8}$	reject brute force	Ex 5
F	Degenerate / empty input	size $= 1$ or $0$	no valid answer exists	Ex 6
G	Word problem (real world)	model then count	translate words → count	Ex 7
H	Exam trap (growth vs bound)	compare two formulas	"exponential = bad" myth	Ex 8

The danger case column is the whole point: a case is not covered until you've shown what happens at its edge.

Figure — Brute force — exhaustive search, when acceptable

Ex 1 — Cell A: unordered pairs (and the double-count edge)

Count the candidates. Why this step? Brute force always starts by sizing the space. One candidate = one unordered pair of positions. With $n = 5$ that is $(2 5) = \frac{5 \cdot 4}{2} = 10 pairs .$ Not $25$ — because $(i, j)$ and $(j, i)$ are the same pair, and a number can't pair with itself.
Enumerate without double-counting. Why this step? If we let the inner loop run from $0$ we'd visit each pair twice and waste half the work (and possibly report a "pair" of an element with itself, distance $0$ , which is wrong). Fix: inner loop starts at i+1.

def closest_pair(a):
    n = len(a); best = None
    for i in range(n):
        for j in range(i+1, n):     # j > i  -> distinct, no double count
            d = abs(a[i]-a[j])
            if best is None or d < best[0]:
                best = (d, i, j)
    return best

Run it by hand on the closest region. Sorted values are $1, 3, 5, 8, 11$ ; the tightest gap is $3$ and $5$ (distance $2$ ), at positions $2$ (value $5$ ) and $4$ (value $3$ ). All other adjacent gaps ( $1 - 3 = 2$ too!) — check: $∣1 - 3∣ = 2$ as well. So there are two pairs at distance $2$ ; brute force returns the first one it meets in loop order.

Verify: number of pairs $= (2 5) = 10$ . Minimum distance over all pairs $= 2$ (from ${1, 3}$ and ${3, 5}$ ). ✔

Ex 2 — Cell B: all subsets, including the empty set

Count. Why? Each of the $3$ items is independently in or out → $2^{3} = 8$ subsets. Crucially this includes the empty set (mask $= 0$ , sum $= 0$ ).
Enumerate with bitmasks. Why bitmasks? A number mask from $0$ to $2^{n} - 1$ has one bit per item; bit $i$ set ⇔ item $i$ chosen. This is the cleanest way to hit all $2^{n}$ subsets exactly once (see Bitmasking).

def has_subset_sum(vals, target):
    n = len(vals)
    for mask in range(1 << n):          # 0 .. 2^n - 1  (includes mask=0)
        s = sum(vals[i] for i in range(n) if mask & (1 << i))
        if s == target:
            return True
    return False

Walk the winning mask. Why? We want to see the answer, not just trust it. Mask $= 10 1_{2} = 5$ selects items $0$ and $2$ → values $2 + 7 = 9$ (no). Mask $= 01 1_{2} = 3$ selects items $0, 1$ → $2 + 3 = 5$ ✔. So the answer is True.
The $n = 0$ edge. Why cover it? Empty input breaks naive code. Here $2^{0} = 1$ : the loop runs once with mask=0, sum $= 0$ . So an empty item list can only match target = 0.

Verify: number of subsets $= 2^{3} = 8$ . Subset ${2, 3}$ sums to $5$ → answer True. Empty-list on target $0$ → True; on target $5$ → False. ✔

Ex 3 — Cell C: all permutations (is $n$ small enough?)

Count. Why? The tour is a permutation of the non-start cities ${1, 2, 3}$ . Number of orderings $= 3! = 6$ . (If we fixed the start, permuting all $4$ would over-count rotations — fixing city $0$ removes that.)
Feasibility check first. Why? Permutation brute force is only safe for tiny $n$ . Rule of thumb: $n!$ must stay under $\sim 1 0^{8}$ . Here $3! = 6$ — trivially fine. For $10$ cities it's $9! = 362880$ (still fine); for $14$ cities $13! \approx 6.2 \times 1 0^{9}$ — too slow, switch to Dynamic Programming (Held–Karp).

from itertools import permutations
def best_tour(cost):
    n = len(cost); best = None
    for perm in permutations(range(1, n)):   # (n-1)! orders
        route = [0] + list(perm) + [0]
        d = sum(cost[route[k]][route[k+1]] for k in range(len(route)-1))
        best = d if best is None else min(best, d)
    return best

Hand-check one small case. Let costs be $c_{01} = 1, c_{02} = 2, c_{03} = 3, c_{12} = 1, c_{13} = 5, c_{23} = 1$ . Route $0 \to 1 \to 2 \to 3 \to 0 = 1 + 1 + 1 + 3 = 6$ . Route $0 \to 2 \to 1 \to 3 \to 0 = 2 + 1 + 5 + 3 = 11$ . Best over all $6$ is 6.

Verify: number of tours $= (4 - 1)! = 6$ . Minimum tour length for the given matrix $= 6$ . ✔

Ex 4 — Cell D: $k$ -tuples over an alphabet (short code = weak)

Count the tuples. Why? Each of the $k = 3$ positions independently picks one of $b = 26$ symbols → $b^{k} = 2 6^{3}$ candidates. $2 6^{3} = 17576.$ Under $1 0^{8}$ , so it cracks instantly.
Compare with the PIN. Why? To see that alphabet size and length trade off. A $6$ -digit PIN is $b = 10, k = 6$ : $1 0^{6} = 1, 000, 000$ . So the $6$ -digit PIN actually has more candidates than the $3$ -letter password — length matters more than you'd guess.
The lesson. Why? This is exactly why short codes are weak (parent note, Ex 3): $b^{k}$ only becomes attacker-proof when $k$ is large. $12$ lowercase letters give $2 6^{12} \approx 9.5 \times 1 0^{16}$ — now brute force fails, as it should.

Verify: $2 6^{3} = 17576$ ; $1 0^{6} = 1000000$ ; so the PIN space is larger by a factor $1000000/17576$ . ✔

Ex 5 — Cell E: the feasibility limit (reject brute force)

Estimate the work. Why? The parent's feasibility test: $N = (space size) \times (verify cost)$ . Here $N = (2 n) \approx \frac{n ^{2}}{2} = \frac{( 1 0 ^{5} ) ^{2}}{2} = 5 \times 1 0^{9} .$
Compare to the line in the sand. Why? $1 0^{8}$ ops/sec is roughly one second of compute. $5 \times 1 0^{9} ≫ 1 0^{8}$ , so brute force needs ~50 seconds — it will time out. Reject it; use a hash set ( $O (n)$ ) or sort + two pointers (see Time Complexity & Big-O).
Where's the boundary? Why? Solve $\frac{n ^{2}}{2} = 1 0^{8} \Rightarrow n = 2 \times 1 0^{8} \approx 14142$ . So $Θ (n^{2})$ brute force is fine up to about $n \approx 1.4 \times 1 0^{4}$ and hopeless well before $1 0^{5}$ — matching the parent's table row " $n \leq 5000$ : maybe".

Verify: $(2 1 0 ^{5}) \approx 5 \times 1 0^{9} > 1 0^{8}$ (reject). Break-even $n = 2 \cdot 1 0^{8} \approx 14142$ . ✔

Ex 6 — Cell F: degenerate / empty input (no valid answer)

Count candidates for each. Why? A pair needs two distinct positions.
- (a) $n = 0$ : $(2 0) = 0$ pairs → loop body never runs → returns None.
- (b) $n = 1$ : $(2 1) = 0$ pairs → also None. A single element cannot pair with itself.
- (c) $n = 2$ : $(2 2) = 1$ pair → checks $3 + 4 = 7$ ✔ → returns $(0, 1)$ .
Why this matters. Why? The dangerous case is $n \leq 1$ : naive code that assumes "there's always a pair" crashes or returns garbage. The correct brute force simply enumerates zero candidates and reports "no answer" — which is the right behaviour.
The general rule. Why? Empty enumeration ⇒ empty answer. Brute force is automatically correct on degenerate inputs as long as you don't special-case wrongly.

Verify: pairs for $n = 0, 1, 2$ are $0, 0, 1$ ; only case (c) succeeds, returning indices $(0, 1)$ with $3 + 4 = 7$ . ✔

Ex 7 — Cell G: a real-world word problem

Model it as tuples. Why? "At most $3$ coins, each of $3$ types" → we try every multiset of size $0..3$ . A clean brute force enumerates counts $(c_{1}, c_{3}, c_{4})$ with $c_{1} + c_{3} + c_{4} \leq 3$ .

def fewest_coins(target, coins=(1,3,4), cap=3):
    best = None
    for c1 in range(cap+1):
      for c3 in range(cap+1):
        for c4 in range(cap+1):
          if c1+c3+c4 <= cap:
            if 1*c1 + 3*c3 + 4*c4 == target:
              used = c1+c3+c4
              best = used if best is None else min(best, used)
    return best

Search for total $6$ . Why enumerate? No greedy shortcut is guaranteed for arbitrary coin sets (greedy can fail — see Greedy Algorithms). Brute force is the safe baseline. Candidates hitting $6$ : $3 + 3$ (two coins), ${1, 1, 4}$ (three coins), ${1, 1, ...}$ ... The minimum is $2$ coins ( $3 + 3$ ).
Real-world caveat. Why the cap? Without the " $\leq 3$ coins" cap the space is infinite, so brute force needs a bound. For unbounded change, this becomes a Dynamic Programming problem.

Verify: $3 + 3 = 6$ using $2$ coins; no single coin equals $6$ , so minimum is $2$ . ✔

Ex 8 — Cell H: the exam trap (growth rate vs input bound)

Plug in the bounds. Why? Big-O is meaningless without the constraint. Compute actual operation counts: $2^{18} = 262144, (1 0^{5})^{2} = 1 0^{10} .$
Compare. Why? $2^{18} \approx 2.6 \times 1 0^{5}$ is ~38000× smaller than $1 0^{10}$ . So the "exponential" P finishes almost instantly while the "polynomial" Q times out. The exam's claim is false.
The takeaway. Why? Growth rate ranks algorithms as $n \to \infty$ on the same input, not across different bounds. Always substitute the given constraint before discarding brute force. This is precisely the parent note's steel-man mistake.

Verify: $2^{18} = 262144 < 1 0^{10} = (1 0^{5})^{2}$ , so P does fewer operations. ✔

Recall Which cell? (self-test)

"Find all pairs summing to $t$ " — which shape? ::: Cell A, unordered pairs, $(2 n)$ . "Try every ordering of jobs" — which shape? ::: Cell C, permutations, $n!$ . "Every subset that fits a knapsack" — which shape? ::: Cell B, subsets, $2^{n}$ . "Guess a PIN of length $k$ " — which shape? ::: Cell D, $k$ -tuples, $b^{k}$ . Break-even $n$ for $Θ (n^{2})$ under $1 0^{8}$ ops? ::: about $14142$ ( $2 \times 1 0^{8}$ ).

See also: Backtracking (brute force that prunes dead branches early), NP-Hard Problems (where brute force + pruning is often all we have), and the Hinglish version.