Brute force — exhaustive search, when acceptable: Visual walkthrough

This is the visual backbone of the parent topic. If you want the Hindi walkthrough, see the Hinglish version.

Step 1 — The atom of everything: one choice, two boxes

WHAT. Before any formula, the smallest possible decision: you have one item, and it can go into one of two boxes — call them "IN" and "OUT". That's it. One item, two possibilities.

WHY start here? Because every brute-force count is secretly just this atom repeated. If you understand "1 item → 2 outcomes", you understand $2^{n}$ , and with a small twist, everything else. We refuse to write $2^{n}$ until you've watched where the $2$ comes from.

PICTURE. The red item drops into either the left box or the right box — two arrows, two futures.

Figure — Brute force — exhaustive search, when acceptable

Step 2 — Two items: choices multiply, they don't add

WHAT. Add a second item. Item A still has its 2 options (IN/OUT). For each of those, item B independently also has 2 options. So we don't get $2 + 2$ ; we get $2$ branches, each splitting into $2$ again → $2 \times 2 = 4$ complete outcomes.

WHY multiply and not add? This is the single most important idea on the page, so let's earn it. "Add" would be right if the choices were alternatives (do A or do B). But here the choices stack — you decide A and then decide B. Every A-branch carries a full copy of the B-choice underneath it. Copies-of-copies is multiplication. Look at the tree: level 1 has 2 nodes, level 2 has $2$ children per node $= 4$ .

PICTURE. A branching tree. The red path traces one complete outcome (A=OUT, B=IN) out of the four leaves.

Step 3 — $n$ items with 2 options each → the $2^{n}$ subset count

WHAT. Now do $n$ items, every one an independent IN/OUT switch. Plug into the multiplication rule with every $m_{k} = 2$ : $item 1 2 \times item 2 2 \times \dots \times item n 2 = 2^{n}$

WHY does this equal "number of subsets"? A subset is exactly a choice of which elements are IN. So "list of IN/OUT switches" and "subset" are the same object wearing different clothes. Counting the switch-settings is counting the subsets — hence $2^{n}$ subsets, matching the parent note exactly.

PICTURE. A doubling staircase: 1 item → 2, 2 items → 4, 3 → 8, 4 → 16. The red curve rises through the flat black budget line — the moment it crosses is the moment brute force starts to time out.

Step 4 — Change the options-per-choice: alphabet $b$ , length $k$ → $b^{k}$

WHAT. Keep the multiplication rule but change how many options each choice has. A PIN of length $k$ over $10$ digits: each of the $k$ slots has $b = 10$ options. $slot 1 b \times slot 2 b \times \dots \times slot k b = b^{k}$

WHY is this the same formula as $2^{n}$ ? Because $2^{n}$ was just $b^{k}$ with $b = 2$ , $k = n$ . Subsets are PINs over a 2-letter alphabet ("IN","OUT"). One rule, two costumes. For a 4-digit PIN, $1 0^{4} = 10000$ — tiny, so the parent's crack loop finishes instantly. That's why short PINs are weak.

PICTURE. A row of $k$ slots, each a red dial showing $b$ ticks; the caption multiplies them out.

Step 5 — When choices shrink: permutations give $n!$

WHAT. Now the twist. Arrange $n$ distinct items into $n$ ordered slots. Slot 1: any of $n$ items. But once one is placed, it's used up — slot 2 has only $n - 1$ left, slot 3 has $n - 2$ , … the last slot has $1$ . The options shrink by one each step: $slot 1 n \times slot 2 (n - 1) \times \dots \times 2 \times last slot 1 = n!$

WHY shrinking? Because reuse is forbidden — you can't place the same item twice. Contrast Step 4, where a digit could repeat (the same $b$ every slot). Repetition allowed → constant options → $b^{k}$ . Repetition forbidden → dwindling options → $n!$ . The only difference between an exponential and a factorial is whether the pool refills.

PICTURE. A funnel of slots: the first slot fed by all $n$ red tokens, each later slot fed by a visibly smaller pool.

Step 6 — Unordered pairs: $n^{2}$ , then halve → $(2 n)$

WHAT. Choose 2 items where order doesn't matter. Two sub-steps. First, ordered pairs: slot 1 = $n$ options, slot 2 = $n - 1$ (no reuse) → $n (n - 1)$ . But $(A, B)$ and $(B, A)$ are the same unordered pair, so we've counted everything twice. Divide by 2: $halve the double-count \frac{n ( n - 1 )}{2} = (2 n) = Θ (n^{2})$

WHY divide by exactly 2? Because a pair of 2 things can be written in $2! = 2$ orders, and every unordered pair shows up in all of its orderings among the ordered count. Two orderings collapse to one → divide by 2. This is precisely why the parent's Two-Sum loop writes for j in range(i+1, n) — starting at i+1 visits each unordered pair once, the built-in halving.

PICTURE. An $n \times n$ grid of cells. The black diagonal (self-pairs $i = i$ , forbidden) is crossed out; the two triangles are mirror images; only the red upper triangle is kept.

Step 7 — Degenerate & edge cases (never leave a gap)

WHAT. The formulas must survive the weird inputs. Walk each:

Input	Formula says	Meaning — is it sane?
$n = 0$ subsets	$2^{0} = 1$	Yes: the empty set is the one subset of nothing.
$n = 0$ permutations	$0! = 1$	Yes: exactly one way to arrange nothing (the empty arrangement).
$n = 1$ pairs	$(2 1) = \frac{1 \cdot 0}{2} = 0$	Yes: you can't pick 2 distinct items from 1.
$k = 0$ PIN	$b^{0} = 1$	Yes: the empty string is the one length-0 PIN.
$b = 1$ alphabet	$1^{k} = 1$	Yes: with one symbol, only one string exists.

WHY check these? A brute-force loop must not crash or miss on the boundary. range(1 << 0) is range(1) — it runs once, correctly enumerating the empty subset. If your formula gave $0$ there, your loop would skip a real candidate. The math and the loop agree at the edges — that's the safety proof.

PICTURE. A number line of $n = 0, 1, 2$ showing each count landing on its true value, with the $n = 0$ cases (which surprise people) circled in red.

Recall Why is

$0! = 1$ and not $0$ ? An arrangement of an empty set of items ::: there is exactly one — the arrangement that places nothing. Zero ways to fail leaves one valid (empty) outcome. It also keeps $n! = n \times (n - 1)!$ consistent at $n = 1$ : $1! = 1 \times 0! = 1$ .

The one-picture summary

Everything above is one rule — multiply the options at each step — bent four ways:

options constant at 2 → $2^{n}$ (subsets)
options constant at $b$ → $b^{k}$ (tuples/PINs)
options draining $n, n - 1, \dots, 1$ → $n!$ (permutations)
options draining for 2 steps, then halve → $(2 n) = Θ (n^{2})$ (pairs)

The red curves ( $2^{n}$ , $n!$ ) rocket past the black $1 0^{8}$ budget line almost immediately; the black curves ( $n^{2}$ , $n lo g n$ ) crawl. That gap is the entire reason Dynamic Programming, Greedy Algorithms, and pruning for NP-Hard Problems exist.

Recall Feynman: the whole walkthrough in plain words

Counting how many things brute force must try is always the same game: at each step, ask "how many ways can this step go?" and multiply those numbers together. If every step is a yes/no switch, you multiply a bunch of 2's and get $2^{n}$ — that's every subset. If each step is a digit, you multiply 10's and get $1 0^{k}$ — that's every PIN. If you're lining people up and can't reuse anyone, the number of choices shrinks each step — $n$ , then $n - 1$ , then $n - 2$ — and multiplying those gives $n!$ . If you just want a pair and don't care about order, count them as ordered ( $n$ times $n - 1$ ) and then cut in half because you counted each pair both ways. The scary part isn't the formulas — it's that $2^{n}$ and $n!$ shoot up so fast that after about $n = 20$ or so, "try everything" would take longer than the universe has been around. That single fact is why we ever bother inventing cleverer algorithms.