Skip to main content

Brute Force Is a Baseline, Not an Insult

What This Concept Is​

Brute force means systematic enumeration of every candidate solution, checking each against the constraints, and keeping the ones that win. It is sometimes called complete search (Halim) or exhaustive search (CLRS/Skiena).

It is the default for a new problem. Before you design a clever algorithm, you should be able to:

  • Enumerate every subset, permutation, pair, partition, or assignment the problem requires.
  • Check each candidate in polynomial time.
  • State the resulting runtime honestly (often $2^n \cdot n$, $n!$, or $n^k$ for some small $k$).

A brute-force solution clarifies the problem, gives you ground-truth answers for testing (concept 15), and defines the bar any "smart" algorithm must beat. It is also the first thing you should sanity-check against before claiming your optimized version is correct.

Brute force is not one algorithm but a family, indexed by the structure of the candidate space:

  • Subset enumeration via bitmasks: $2^n$ candidates, each checked in $O(n)$ or $O(n^2)$.
  • Permutation enumeration via recursion or itertools.permutations: $n!$ candidates.
  • Cartesian product for choose-one-per-group problems: $\prod_i |G_i|$ candidates.
  • Tree enumeration via recursion for trees of possibilities: size depends on branching and depth.

Why It Matters Here​

Many later paradigms are optimizations of brute force:

  • Backtracking is brute force with feasibility pruning (concept 11).
  • Branch-and-bound is brute force with heuristic cutoffs and optimality pruning.
  • Divide-and-conquer and DP often start as "try every split" and then avoid recomputation by memoization (cluster 4).
  • Greedy algorithms are the subset of brute force where one local choice is provably optimal (concept 10).

You cannot explain why an algorithm is "fast" unless you can explain what the brute force would have done. Every complexity improvement is the difference between two candidate counts, and the optimizer who cannot enumerate at all cannot see the structure that makes the improvement possible.

A secondary benefit: brute force is often the right answer. A competition problem with $n \le 20$ expects a $2^n$ bitmask solution; a spec test that runs once on 50 records does not need asymptotics-first thinking. Contest sizing rules of thumb (Halim): $n \le 11$ accepts $n!$; $n \le 25$ accepts $2^n \cdot n$; $n \le 10^4$ accepts $n^2$; $n \le 10^6$ accepts $n \log n$; $n \le 10^8$ expects $n$ with tight constants.

Concrete Example​

Example 1 (subset sum, decision). Given $A = [a_1, \ldots, a_n]$ and target $T$, does any subset sum to $T$?

Brute force: enumerate all $2^n$ subsets, sum each, check. Runtime $\Theta(n \cdot 2^n)$.

def subset_sum_brute(A, T):
    n = len(A)
    for mask in range(1 << n):
        s = sum(A[i] for i in range(n) if mask & (1 << i))
        if s == T:
            return True
    return False

For $n = 20$, $2^{20} \approx 10^6$ masks and $\sim 2 \times 10^7$ work. Finishes in under a second. For $n = 40$, it is $10^{12}$ and intractable - but meet-in-the-middle splits into two halves of $2^{20}$ each and sorts/hashes (see cluster 4). You can only see that improvement if you first see the brute force.

Example 2 (traveling salesman on $n$ cities). Brute force tries all $n!$ orderings, picks the cheapest. For $n = 10$, $10! \approx 3.6 \times 10^6$ - fine. For $n = 20$, $n!$ is already $2.4 \times 10^{18}$ - intractable, but the bitmask Held-Karp DP in $O(n^2 2^n)$ handles $n \approx 20$ in a second.

Example 3 (3SUM). Find indices $i < j < k$ with $a_i + a_j + a_k = 0$. Brute force: $\binom{n}{3} = \Theta(n^3)$. Better: sort plus two pointers in $\Theta(n^2)$. Even better: hash-based variants in $\Theta(n^2)$. A sub-quadratic algorithm is open (3SUM conjecture) - and you only appreciate that once you have the brute force as the obvious baseline.

Example 4 (all-pairs distance $\le k$). Try every pair: $\Theta(n^2)$. For dense outputs (many pairs qualify), this is actually optimal - you cannot output more pairs than you check. Not every brute force is slow.

Common Confusion / Misconceptions​

  • "Brute force is bad, I should always optimize." No. Brute force is the reference implementation. Optimizing is only justified when the brute-force runtime is too large for the input range; otherwise you are inventing complexity for no reason. In industry, readable $O(n^2)$ frequently ships over clever $O(n \log n)$.
  • "Brute force means ugly code." A brute-force subset enumeration or permutation generator should be clean, testable, and obviously correct. That is precisely why it works as a test oracle. Ugly brute force defeats its own purpose.
  • "Brute force is never optimal." It can be. Output-sensitive problems (all pairs within distance $k$; all pairs with a shared attribute) are $\Omega(\text{output})$, so a brute-force check-every-pair algorithm matches the lower bound on dense outputs.
  • "Brute force and backtracking are the same." Brute force enumerates; backtracking enumerates and prunes infeasible branches. Without pruning, backtracking degrades to brute force (concept 11).
  • "Brute force always runs slowly." With small enough $n$, it runs instantly. Your code does not know whether $n = 15$ or $n = 15{,}000$; you decide by sizing the candidate space. "Acceptable" is a function of constraints, not of the algorithm's name.
  • "The brute force for subset-style problems is always $2^n$." True for plain subsets, but many problems ask for structured subsets (e.g. all $k$-subsets): $\binom{n}{k}$ is smaller and admits a different enumeration scheme. Pick the smallest candidate space that covers the answer, not the first one that comes to mind.

How To Use It​

When starting a new problem:

  1. Name the candidate space. Subsets? Orderings? Pairs? Trees? Partitions?
  2. Size it as a function of $n$: $2^n$, $n!$, $n^k$, $C(n, k)$.
  3. Describe how to check one candidate. What is the cost of validation - $O(1)$, $O(n)$, $O(n^2)$?
  4. Multiply. That is your brute-force runtime.
  5. Decide whether that is acceptable for the given constraints. If yes, implement it - done. If not, you have a target to beat.
  6. Implement brute force anyway. It is the correctness oracle for the optimized version on small inputs.
  7. State the optimization insight in one line ("subsets of size $k$ from disjoint halves can be combined without enumerating both"). That line is the bridge from brute force to the real algorithm.

Always keep the brute-force implementation around during development. In competitive programming, this is known as writing a stupid solution alongside a smart solution; in production engineering, it is the regression oracle.

When in doubt, implement the brute force before the smart solution. Many bug reports on the smart algorithm resolve in minutes once you can run both side-by-side on the reported input. Do not delete the brute force after shipping - keep it as a CI-enabled stress-test target.

Transfer / Where This Shows Up Later​

  • S1 M5 (problem solving) said "restate the problem and size the candidate space." This page is the operational version.
  • S4 (systems) uses brute-force baselines to sanity-check compiler optimizations and cache-oblivious algorithms; the "naive loop" is the reference against which optimizations are benchmarked.
  • S5 (OS) uses brute-force schedulers (exhaustive feasibility search) offline to validate heuristic schedulers.
  • S6 (databases) runs the brute-force Cartesian product as a semantic fallback for join verification even when the planner emits a clever plan; it is the oracle for query correctness.
  • S7 (architecture) writes fitness functions by comparing proposed architectures to a brute-force "enumerate all possible coupling matrices" oracle for small modules.
  • S8 (distributed systems) uses brute-force state-exploration (TLA+, model checking) to verify protocols; the model checker is the exhaustive search.

Concept 11 (backtracking) is brute force plus pruning; concept 15 (testing) uses brute force as the stress-test oracle; cluster 4 converts brute force into DP when subproblems overlap.

Within this semester: S2 M2-M3 use a brute-force baseline (e.g., $O(n^2)$ edge scan) to sanity-check graph algorithms before optimizing; S2 M4 literally derives every DP by starting from a recursive brute force and memoizing; S2 M5 relies on brute-force oracles for randomized data structures where correctness is more subtle than wall-clock.

Check Yourself​

  1. What is the brute-force runtime for 3SUM (find $a + b + c = 0$ among $n$ integers)?
  2. Why is having a brute-force implementation useful when writing tests for an optimized version?
  3. When is brute force the "right" algorithm and not just a starting point?
  4. You have $n = 22$ items and need to find the max-value subset under a weight cap. What is the brute-force runtime, and does it fit in 1 second?
  5. Give a problem where the candidate space is $\Theta(n!)$ but brute force is still viable because of a symmetry cutting it to $(n-1)!$.
  6. For each candidate space, name the canonical iteration idiom in Python:
    • All subsets of $n$ items (expect bitmasks or itertools.chain).
    • All permutations of $n$ items (expect itertools.permutations).
    • All length-$k$ combinations (expect itertools.combinations).
    • Cartesian product of groups (expect itertools.product).

Mini Drill or Application​

For each problem, describe the candidate space, its size, and the per-candidate check.

  1. Find the $k$-element subset of an array with the largest sum.
  2. Count the number of Hamiltonian paths in a graph on $n$ vertices.
  3. Find the maximum-product pair in an array.
  4. Determine whether a sudoku board has a solution (before pruning).
  5. Given $n$ students and $n$ projects, find the assignment maximizing total preference (bipartite matching, brute force).
  6. Implementation drill. Write two versions of "max sum of a contiguous subarray":
    • Brute force: all $\binom{n}{2}$ subarrays, sum each in $O(n)$ (or $O(1)$ with prefix sums). Complexity $\Theta(n^3)$ or $\Theta(n^2)$.
    • Smart: Kadane's in $\Theta(n)$. Stress-test the smart version against brute for $n \le 50$ and 500 random inputs. Any disagreement is a bug; the brute version is the oracle.

Read This Only If Stuck​