Brute force — exhaustive search, when acceptable: Exercises

Before we start, here is the mental picture we keep reusing — the whole game is counting how big the pile of candidates is, then asking if the pile is small enough to walk through.

Figure — Brute force — exhaustive search, when acceptable

Level 1 — Recognition

Goal: read a constraint and name the search-space size + verdict. No coding.

Exercise 1.1

A problem says: "given $n \leq 22$ items, consider every subset." How many subsets are there, and will brute force fit under $1 0^{8}$ ?

Recall Solution 1.1

WHAT we count: every subset. WHY $2^{n}$ : each of the $n$ items is independently in or out — that's $2$ choices, made $n$ times, so $n 2 \cdot 2 \dots 2 = 2^{n}$ . With $n = 22$ : $2^{22} = 4194304 \approx 4.19 \times 1 0^{6}$ . Since $4.19 \times 1 0^{6} < 1 0^{8}$ , brute force is fine (even multiplied by a small per-subset cost).

Exercise 1.2

A problem has $n \leq 12$ and asks you to try every ordering (permutation) of the items. Size? Verdict?

Recall Solution 1.2

WHY $n!$ : the first slot has $n$ choices, the next $n - 1$ (one item used up), and so on down to $1$ . Multiply: $n \cdot (n - 1) \dots 1 = n!$ . $12! = 479001600 \approx 4.79 \times 1 0^{8}$ . That is above $1 0^{8}$ . So bare permutation brute force is borderline-to-risky — likely too slow unless verification is trivial and constants are tiny. Prefer pruning (backtracking) or DP here.

Exercise 1.3

"Find any two indices $i < j$ with $a_{i} + a_{j} = t$ ; $n \leq 5000$ ." Which enumeration, what size, verdict?

Recall Solution 1.3

WHAT: enumerate all unordered distinct pairs. WHY $(2 n)$ : pick slot 1 ( $n$ ways) and slot 2 ( $n - 1$ ways), then divide by $2$ because $(i, j)$ and $(j, i)$ are the same pair: $\frac{n ( n - 1 )}{2}$ . $n = 5000$ : $\frac{5000 \cdot 4999}{2} = 12497500 \approx 1.25 \times 1 0^{7} < 1 0^{8}$ . Brute force OK.

Level 2 — Application

Goal: write the enumeration loop / mask and count its cost.

Exercise 2.1

Write brute force that returns all index pairs $(i, j)$ , $i < j$ , with $a_{i} + a_{j} = t$ . State the exact number of pair-checks for general $n$ .

Recall Solution 2.1

def all_pairs(a, t):
    n = len(a)
    out = []
    for i in range(n):              # first index
        for j in range(i+1, n):     # second index, strictly after i
            if a[i] + a[j] == t:
                out.append((i, j))
    return out

WHY start j at i+1: it enforces $i < j$ , so every unordered pair is visited exactly once — no self-pairs, no duplicates. Number of checks: the inner loop runs $(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2} = (2 n)$ times. This is the $Θ (n^{2})$ we derived. For $n = 5$ that is exactly $10$ checks.

Exercise 2.2

Using bitmasks, count how many subsets of ${0, 1, 2, 3}$ have sum $= 3$ . Show the masks.

Recall Solution 2.2

WHY masks: a number mask from $0$ to $2^{4} - 1 = 15$ encodes a subset — bit $i$ set $\Leftrightarrow$ element $i$ is chosen. This realises the $2^{4} = 16$ count. Subsets summing to $3$ :

${3}$ → mask $100 0_{2} = 8$ , sum $3$ ✓
${0, 3}$ → mask $100 1_{2} = 9$ , sum $0 + 3 = 3$ ✓
${1, 2}$ → mask $011 0_{2} = 6$ , sum $1 + 2 = 3$ ✓
${0, 1, 2}$ → mask $011 1_{2} = 7$ , sum $0 + 1 + 2 = 3$ ✓

That's 4 subsets. (Check: no other combination of ${0, 1, 2, 3}$ totals $3$ .)

Exercise 2.3

A length-3 password uses lowercase letters $a$ – $z$ . How many candidates must brute force try in the worst case? Is that instant?

Recall Solution 2.3

WHY $b^{k}$ : each of the $k = 3$ positions is filled independently from an alphabet of size $b = 26$ , so $26 \times 26 \times 26 = 2 6^{3}$ . $2 6^{3} = 17576$ . That's way under $1 0^{8}$ — effectively instant. (This is exactly why 3-character passwords are worthless.)

Level 3 — Analysis

Goal: separate enumeration cost from verify cost, and reason about totals.

Exercise 3.1

A brute force enumerates all $2^{n}$ subsets, and for each subset spends $Θ (n)$ time scanning the bits to compute its weight. Give the total cost and the largest $n$ that stays under $1 0^{8}$ .

Recall Solution 3.1

Total cost $= (candidates) \times (verify each) = 2^{n} \cdot n$ . We want $2^{n} \cdot n \leq 1 0^{8}$ .

$n = 20$ : $2^{20} \cdot 20 = 1048576 \cdot 20 = 20971520 \approx 2.1 \times 1 0^{7}$ ✓
$n = 21$ : $2^{21} \cdot 21 = 2097152 \cdot 21 = 44040192 \approx 4.4 \times 1 0^{7}$ ✓
$n = 22$ : $2^{22} \cdot 22 = 4194304 \cdot 22 = 92274688 \approx 9.23 \times 1 0^{7}$ ✓ (just under)
$n = 23$ : $2^{23} \cdot 23 = 8388608 \cdot 23 = 192937984 \approx 1.93 \times 1 0^{8}$ ✗

So the largest safe $n$ is $22$ .

Exercise 3.2

Two solutions to the same problem: (A) brute force $O (2^{n})$ with the given bound $n = 18$ ; (B) a "clever" $O (n^{2})$ algorithm run on a different problem where $n = 1 0^{5}$ . Which does fewer operations?

Recall Solution 3.2

(A): $2^{18} = 262144 \approx 2.6 \times 1 0^{5}$ .
(B): $(1 0^{5})^{2} = 1 0^{10}$ . (A) does ~ $40000 \times$ fewer operations. Moral: "exponential" is not automatically slower than "polynomial" — the input bound decides. A tiny $n$ tames the exponential.

Exercise 3.3

A subset-sum brute force updates its running best like this:

best = max(best, val)   # <-- placed BEFORE the weight check
if wt <= W:
    pass

What is wrong, and what does it return in the worst case?

Recall Solution 3.3

Bug: it scores the subset (max(best, val)) before confirming the subset is feasible (wt <= W). So it can adopt the value of an overweight, illegal subset. Worst case: the heaviest, highest-value subset — which violates $W$ — wins, returning a value that no legal packing can achieve. The answer is an over-estimate. Fix: verify the constraint first, then score:

if wt <= W:
    best = max(best, val)

Level 4 — Synthesis

Goal: combine enumeration + pruning + a feasibility decision into a full plan.

Exercise 4.1

Knapsack-style: weights=[2,3,4,5], values=[3,4,5,6], cap W=5. By full subset enumeration, find the max value with total weight $\leq 5$ . Show the reasoning.

Recall Solution 4.1

Enumerate all $2^{4} = 16$ subsets; keep only those with weight $\leq 5$ ; take the best value. Feasible subsets and their (weight, value):

${}$ → (0, 0)
${0}$ → (2, 3)
${1}$ → (3, 4)
${2}$ → (4, 5)
${3}$ → (5, 6)
${0, 1}$ → (5, 7) ← weight exactly 5, value 7
${0, 2}$ → (6, —) infeasible
all larger subsets exceed 5.

Best feasible value = 7, from taking items $0$ and $1$ (weight $2 + 3 = 5$ , value $3 + 4 = 7$ ).

Exercise 4.2

You must solve the same knapsack but with $n = 40$ items. Pure brute force needs $2^{40} \cdot 40$ operations. Estimate it, decide whether it's acceptable, and name the right paradigm.

Recall Solution 4.2

$2^{40} \approx 1.0995 \times 1 0^{12}$ , times $40 \approx 4.4 \times 1 0^{13}$ operations. That is $\sim 440000 \times$ over the $1 0^{8}$ budget — hopeless by brute force. Structure exists (overlapping subproblems / optimal substructure), so use DP: knapsack in $O (nW)$ . With a moderate $W$ this is trivial. (If $n \leq 40$ but no small $W$ , meet-in-the-middle via Bitmasking splits into two halves of $2^{20}$ each.)

Exercise 4.3

Design a brute force that finds the shortest route visiting all $n$ cities once (Travelling Salesman). What do you enumerate, what's the size, and for which $n$ is it acceptable?

Recall Solution 4.3

Enumerate: all orderings (permutations) of the cities; fix the start city to kill rotational duplicates, giving $(n - 1)!$ tours. Verify: sum the $n$ leg-distances, $Θ (n)$ each. Total $\approx (n - 1)! \cdot n = n!$ order of work.

$n = 10$ : $10! = 3628800 \approx 3.6 \times 1 0^{6}$ ✓ fine.
$n = 11$ : $11! = 39916800 \approx 4.0 \times 1 0^{7}$ ✓ still OK.
$n = 12$ : $12! \approx 4.8 \times 1 0^{8}$ ✗ borderline/too slow.

TSP is NP-hard, so beyond ~ $n = 12$ we use Bitmasking-DP (Held–Karp, $O (2^{n} n^{2})$ , good to ~ $n = 20$ ) or heuristics/Backtracking with pruning.

Level 5 — Mastery

Goal: judge trade-offs and pick the paradigm from constraints alone.

Exercise 5.1

For each constraint, state the intended complexity and whether brute force survives. Justify with the $1 0^{8}$ rule. (a) $n \leq 11$ (b) $n \leq 24$ , subsets (c) $n \leq 500$ (d) $n \leq 1 0^{5}$ .

Recall Solution 5.1

(a) $n \leq 11$ → hint of $O (n!)$ ; $11! \approx 4.0 \times 1 0^{7} < 1 0^{8}$ → brute force (permutations) OK. (b) $n \leq 24$ , subsets → $2^{24} = 16777216 \approx 1.68 \times 1 0^{7}$ ; even $\times 24$ is $\approx 4.0 \times 1 0^{8}$ (a bit over), so plain $O (2^{n})$ OK, $O (2^{n} \cdot n)$ borderline — use meet-in-the-middle if verify is heavy. (c) $n \leq 500$ → $O (n^{3}) = 1.25 \times 1 0^{8}$ ; borderline but usually acceptable with light constants. (d) $n \leq 1 0^{5}$ → $O (n^{2}) = 1 0^{10}$ ✗; brute force dies. Target $O (n lo g n) \approx 1.7 \times 1 0^{6}$ ✓.

Exercise 5.2

A judge gives $n \leq 20$ and asks for the best subset under a constraint, hinting bit tricks. Which two paradigms are both viable, and how do you choose?

Recall Solution 5.2

$2^{20} \approx 1 0^{6}$ , so Bitmasking brute force over all subsets is viable and simplest to get right. If the constraint has a knapsack-like weight structure, DP ( $O (nW)$ ) is also viable and can be faster for large $W$ -free structure. Choose by: (i) if enumeration count $\leq 1 0^{8}$ and correctness matters most → bitmask brute force; (ii) if $n$ could grow or $W$ is small → DP. When unsure, code brute force first and use it as a reference tester for the DP.

Exercise 5.3

You wrote a fast DP and want confidence it's correct on $n \leq 15$ cases. Describe how brute force earns its keep here even though the "real" solution is the DP.

Recall Solution 5.3

Use brute force as a differential tester: for many random small inputs ( $n \leq 15$ , where $2^{15} = 32768$ is instant), run both the brute force and the DP and assert their answers match. Because complete enumeration is guaranteed correct, any mismatch localises a bug in the DP. Brute force's slowness is irrelevant at $n \leq 15$ ; its correctness-for-free is the whole point.

Recall Wrap-up: the one-line procedure (EVE)

Enumerate the candidates, Verify each, Estimate size×cost vs $1 0^{8}$ . If the estimate loses, hunt for structure: recurrence → DP, exchange → greedy, prune-partial → Backtracking, all-subsets small → Bitmasking. Complexity language throughout is from Time Complexity & Big-O.