Brute force — exhaustive search, when acceptable

WHAT is brute force?

The two ingredients:

1. Enumeration — a way to list every candidate exactly once (e.g. all subsets, all permutations, all pairs, all integers in a range).
2. Verification — a predicate that checks whether a candidate is a/the answer.

WHY does it work (and why is it slow)?

The price is time. The cost is:

$T = (\text{number of candidates}) \times (\text{cost to verify one})$

The number of candidates usually grows combinatorially. Let's derive the famous ones from first principles.

So total time is e.g. $\Theta(2^n \cdot \text{verify})$ for a subset search. These explode fast — which is exactly why we eventually need smarter paradigms (greedy, DP, divide-and-conquer).

WHEN is brute force acceptable?

Accept brute force when any of these hold:

1. Small input bound. If constraints say $n \le 20$ for subsets ($2^{20}\approx 10^6$) or $n \le 10$ for permutations ($10! \approx 3.6\times10^6$), the total fits in the budget (roughly $10^8$ simple operations per second).
2. It's a one-off / not performance-critical. Run-once scripts, config-time computation.
3. You need a correct reference to test an optimized solution against (differential testing).
4. No better algorithm is known (some NP-hard problems — you brute force with pruning).

Reject it when the search space exceeds your time budget and structure exists to exploit.

Worked Example 1 — Two-Sum by brute force

Problem: given array $a$ and target $t$, find indices $i<j$ with $a_i+a_j=t$.

def two_sum_brute(a, t):
    n = len(a)
    for i in range(n):          # candidate first index
        for j in range(i+1, n): # candidate second index
            if a[i] + a[j] == t:
                return (i, j)
    return None

• Why the nested loop? The candidates are unordered pairs; enumerating all $\binom{n}{2}$ pairs covers the whole space exactly once (we start $j$ at $i+1$ to avoid duplicates & self-pairs).
• Why correct? Every valid pair is some $(i,j)$ with $i<j$, and we visit all of them.
• Cost: $\Theta(n^2)$. Acceptable for $n\le$ a few thousand; for $n=10^5$ use a hash set ($O(n)$).

Worked Example 2 — Subset sum (max value under a weight cap)

Problem: pick a subset of items maximizing total value with total weight $\le W$.

def best_subset(weights, values, W):
    n = len(weights)
    best = 0
    for mask in range(1 << n):     # all 2^n subsets, encoded as bits
        wt = val = 0
        for i in range(n):
            if mask & (1 << i):    # is item i in this subset?
                wt  += weights[i]
                val += values[i]
        if wt <= W:
            best = max(best, val)
        # Why this step? we only update best for FEASIBLE subsets
    return best

• Why 1 << n masks? A bitmask mask from $0$ to $2^n-1$ enumerates every subset: bit $i$ set ⇔ item $i$ chosen. This realises the $2^n$ count we derived.
• Why correct? Optimal subset is some subset → it is one of the masks → it gets considered.
• Cost: $\Theta(2^n \cdot n)$. Fine for $n\le 20$. Beyond that, switch to DP ($O(nW)$).

Worked Example 3 — Cracking a 4-digit PIN

def crack(check):                       # check(pin) -> True if correct
    for pin in range(10000):            # 10^4 candidates
        s = f"{pin:04d}"
        if check(s):
            return s

• Why $10^4$? Length-4 string over 10 digits → $b^k = 10^4$ candidates. Tiny, so brute force is instant — this is why short PINs are weak.

Flashcards

Connections

• Algorithm Paradigms — brute force is the baseline paradigm
• Time Complexity & Big-O — how we estimate $2^n$, $n!$, $n^2$ growth
• Dynamic Programming — replaces exponential subset/sequence brute force with polynomial DP
• Greedy Algorithms — trades exhaustive checking for a single myopic choice
• Backtracking — brute force with pruning; skips provably-bad branches
• Bitmasking — the standard technique to enumerate subsets
• NP-Hard Problems — where brute force (with pruning) is sometimes the best we know

Concept Map

Hinglish (regional understanding)