Brute force — exhaustive search, when acceptable: Question bank

Before we start, one shared vocabulary reminder so no word here is unearned:

Notation used on this page (every symbol earned first)

Several shorthands appear in the answers below. Since we use them before you'd meet them elsewhere, here is each one in plain words and a picture.

Now the three visuals that carry the reasoning. Each is anchored to the callout right beneath it — look at the picture before reading the words.

Figure — Brute force — exhaustive search, when acceptable

True or false — justify

State true/false, then give the reason — a bare verdict scores nothing.

Brute force is by definition always slower than a "clever" algorithm.

False. Slower asymptotically, but for a given constraint it can win:

2^{18} \approx 2.6 \times 1 0^{5}

beats an

O (n^{2})

method on

n = 1 0^{5}

. Speed is growth-rate relative to the input bound.

Brute force is always correct.

False as stated — it is correct only if the enumeration is complete (misses no candidate) and the verifier is correct. A buggy inner loop that skips candidates breaks correctness.

If a problem's answer exists, exhaustive search is guaranteed to find it.

Only when the search space is finite and fully enumerated. Over an infinite/unbounded space (e.g. all integers) it may run forever and never conclude "no answer".

The cost of brute force is just the number of candidates.

False. Cost

= (number of candidates) \times (cost to verify one)

. A cheap-looking

2^{n}

enumeration with an

O (n)

verify is really

Θ (2^{n} \cdot n)

Exponential time complexity (

2^{n}

) always means the algorithm is unusable.

False. Usability depends on the given

n

. For

n \leq 20

2^{n} \approx 1 0^{6}

is trivially fast; "exponential = forbidden" is a myth that ignores the constraint.

O (n^{2})

brute force is always safe because polynomial time is "efficient".

False. On

n = 1 0^{5}

n^{2} = 1 0^{10}

ops blows past the

\sim 1 0^{8}

/sec budget. Polynomial is not automatically fast at scale — see Time Complexity & Big-O.

Brute force and backtracking are the same thing.

False. Backtracking is an exhaustive search but it prunes dead branches early; pure brute force generates every candidate with no pruning. See Backtracking.

For a subset-search brute force, the number of masks depends on the item weights or values.

False. It depends only on

n

: there are

2^{n}

subsets regardless of the numbers inside them. Values/weights affect verification, not enumeration size.

Enumerating all permutations and all subsets of

n

items cost the same.

False. Subsets

= 2^{n}

, permutations

= n!

. For

n = 12

2^{12} = 4096

12! \approx 4.8 \times 1 0^{8}

— permutations explode far faster.

Brute force always uses little memory since it "just tries things".

False. Memory depends on how you enumerate: an iterative loop over masks is

O (1)

extra space, but a recursive permutation/subset generator holds a call stack of depth

O (n)

, and materialising all candidates in a list costs

O (2^{n})

O (n!)

space — often the real bottleneck.

If brute force times out, the problem must be NP-hard.

False. Timing out just means your enumeration is too big for the budget; a smarter polynomial algorithm (greedy, DP, hashing) may still exist. Hardness is a separate claim — see NP-Hard Problems.

Each line describes a flawed piece of reasoning or code. The reveal names the bug and the fix. (Recall from the parent note's subset-sum example: W is the weight cap — the maximum total weight a chosen subset is allowed to have — and wt is the running total weight of the current subset.)

for i in range(n): for j in range(n): check pair (i,j) — enumerates all pairs correctly.

Error: it double-counts (visits

(i, j)

and

(j, i)

) and includes self-pairs

(i, i)

. Fix: inner loop range(i+1, n) for distinct unordered pairs.

In the subset-sum solver, best = max(best, val) is placed before the wt <= W check (here wt = subset's total weight, W = the allowed weight cap).

Error: this scores infeasible subsets whose total weight wt exceeds the cap W, returning an illegal answer. Fix: verify feasibility (wt <= W) first, then update best.

"The PIN has 4 digits, so there are

4^{10}

candidates to try."

Error: the base and exponent are swapped. It is

b^{k} = 1 0^{4}

(10 choices per position, 4 positions), not

4^{10}

n \leq 24

with

O (2^{n})

is fine, and

2^{24} \approx 1.6 \times 1 0^{7}

, so

2^{40}

for

n = 40

is only a bit more."

Error: exponentials don't scale "a bit".

2^{40} \approx 1 0^{12}

— a factor of ~65000 larger, far past budget. Each

+ 1

n

doubles the work.

"I'll brute-force by trying candidates until I stop finding better ones, then quit early."

Error: stopping early breaks completeness. Without exploring all candidates you may skip a later, better/only-valid one. Pure brute force must check the whole space (only provably safe pruning is allowed — that's backtracking).

"My verifier occasionally rejects a valid candidate, but enumeration is complete, so the search is correct."

Error: correctness needs both halves. A wrong verifier can reject the true answer even if it was enumerated — the answer is examined but wrongly discarded.

"range(1 << n) and range(2 * n) are the same loop for enumerating subsets."

Error: 1 << n equals

2^{n}

(doubling per shift), while 2 * n is just twice

n

. For

n = 10

that's

1024

20

— the second skips almost every subset, so enumeration is grossly incomplete.

Feasibility estimate: "search space is

2^{n}

with

n = 30

, and

2^{30} \approx 1 0^{9}

, so it's fine."

Error:

1 0^{9}

already sits at/above the timeout line (

\sim 1 0^{8}

–

1 0^{9}

ops/sec), and the per-candidate verify cost multiplies it further. This is not safely fine.

Why questions

Why start the inner loop of a pair search at i+1 instead of 0?

To enumerate each unordered pair exactly once and skip self-pairs — this makes the enumeration have no duplicates, giving

(2 n)

candidates instead of

n^{2}

Why does range(1 << n) iterate over exactly

2^{n}

values?

Because 1 << n shifts the single bit of 1 left

n

times, doubling each shift, so it equals

2^{n}

— precisely the subset count from figure s01.

Why is brute force used as a "reference" to test faster algorithms?

Because its correctness is trivial to trust (complete enumeration + simple verify), so its output is a ground truth to compare an optimized solution against on small inputs (differential testing).

Why does each element contributing "in or out" give exactly

2^{n}

subsets?

The

n

choices are independent and each has 2 options, so total

= n 2 \times 2 \times \dots \times 2 = 2^{n}

by the multiplication principle (see figure s01).

Why does the same multiplication principle give

n!

for permutations, not

2^{n}

For subsets each item has a fixed 2 choices; for orderings the choice-count shrinks by one per slot (

n, n - 1, \dots, 1

) because items already placed can't be reused, and

n \times (n - 1) \times \dots \times 1 = n!

Why do we multiply candidate-count by verify-cost rather than add them?

Because the verifier runs once per candidate; it's a nested cost. Total work = candidates

\times

work-per-candidate, which multiplies.

Why can iterative brute force be memory-cheap while recursive brute force is not?

An iterative mask loop keeps only a couple of counters (

O (1)

space), but recursion stacks one frame per depth level, costing

O (n)

stack space — and storing all candidates costs

O (2^{n})

O (n!)

memory.

Why is

1 0^{8}

the rough "line in the sand" for feasibility?

A typical machine does on the order of

1 0^{8}

simple operations per second, so a search near or above that risks exceeding a per-test time budget. See Time Complexity & Big-O.

Why can bitmasks enumerate subsets?

An integer from

0

2^{n} - 1

has

n

bits; reading bit

i

as "item

i

chosen?" makes each integer correspond to exactly one distinct subset — a perfect, gap-free enumeration (see figure s02). See Bitmasking.

Why does knowing brute force still matter if we plan to use DP or greedy?

It's the baseline every clever method is judged against ("how much faster than brute force?"), and it gives the correct reference to validate the optimized version. See Dynamic Programming and Greedy Algorithms.

Why does a short PIN make brute force devastating rather than a defense?

Its search space

1 0^{4}

is tiny, so trying every PIN is instant — the smallness that makes brute force feasible is exactly what makes short secrets weak.

Edge cases

Brute-force subset search with

n = 0

(empty item set) — how many candidates?

Exactly

2^{0} = 1

: the single empty subset. The loop range(1 << 0) = range(1) runs once with mask=0 (since 1 << 0 = 1), correctly considering "take nothing".

Two-sum brute force on an array of length

n = 1

— what happens?

Zero pairs exist (

(2 1) = 0

); the inner loop never runs and the function returns "no answer" — the correct result, since a valid pair needs two distinct indices.

Permutation brute force with

n = 0

(empty item set) — how many candidates?

Exactly

0! = 1

: there is one arrangement of nothing, the empty ordering. This mirrors

2^{0} = 1

for subsets — the "do nothing" case is always a single valid candidate, never zero.

Subset-sum where every item's weight already exceeds the cap W.

Only the empty subset (mask=0, weight 0) is feasible, so best stays at its initial value

0

. The algorithm correctly returns 0, not an infeasible pick.

PIN cracker when the correct PIN is 0000.

The loop starts at pin=0, formatted f"{pin:04d}" = "0000", so it's the first candidate tested — found immediately. The :04d zero-padding is essential or 0 would print as "0" instead of the valid 4-digit "0000".

A search space that is infinite (e.g. "find any real number with property P").

Pure brute force is inapplicable — you cannot enumerate an infinite set exactly once. You need a finite discretization or a smarter method; exhaustive search assumes a finite candidate list.

Permutation brute force with

n = 1

Exactly

1! = 1

permutation (the single item in one order). Degenerate but consistent with

n!

; the base case never breaks the formula.

Memory blow-up: materialising all permutations of

n = 12

into a list before checking.

That stores

12! \approx 4.8 \times 1 0^{8}

orderings — gigabytes of RAM, likely a crash. Fix: stream candidates one at a time (generate-check-discard) so space stays

O (n)

instead of

O (n!)

Feasibility when candidate count is small but verify is expensive, e.g.

1 0^{3}

candidates each needing an

O (n^{2})

check on

n = 1 0^{4}

Total

\approx 1 0^{3} \times 1 0^{8} = 1 0^{11}

— infeasible. Small candidate counts do not guarantee safety; always multiply by verify cost.

Recall Self-check before you leave

Give one case where an "exponential" brute force beats a "polynomial" one.
Which single line turned $n^{2}$ ordered pairs into $(2 n)$ unordered ones?
Name the two conditions that together make brute force correct.
Why is 1 << n equal to $2^{n}$ , and where does that appear in code?
When does brute force cost a lot of memory, not just time?

Question bank — Brute force — exhaustive search, when acceptable

Notation used on this page (every symbol earned first)

True or false — justify

Spot the error

Why questions

Edge cases