Brute force — exhaustive search, when acceptable: Visual walkthrough

3.7.1 · D2 · Coding › Algorithm Paradigms › Brute force — exhaustive search, when acceptable

Yeh parent topic ka visual backbone hai. Agar tum Hindi walkthrough chahte ho, toh Hinglish version dekho.

Step 1 — Har cheez ka atom: ek choice, do boxes

KYA HAI. Kisi bhi formula se pehle, sabse chhota possible decision: tumhare paas ek item hai, aur woh do boxes mein se kisi ek mein ja sakta hai — inhe "IN" aur "OUT" kaho. Bas itna. Ek item, do possibilities.

YE YAHAN SE KYU SHURU KARTE HAIN? Kyunki har brute-force count secretly sirf yahi atom baar baar repeat hota hai. Agar tum "1 item → 2 outcomes" samajh gaye, toh tum $2^{n}$ samajh gaye, aur ek chhoti si twist ke saath, baaki sab bhi. Hum $2^{n}$ likhne se mana karte hain jab tak tum dekh na lo ki $2$ kahaan se aa raha hai.

PICTURE. Red item ya toh left box mein jaata hai ya right box mein — do arrows, do futures.

Figure — Brute force — exhaustive search, when acceptable

Step 2 — Do items: choices multiply hoti hain, add nahi

KYA HAI. Ek doosra item add karo. Item A ke paas abhi bhi uske 2 options hain (IN/OUT). Un mein se har ek ke liye, item B independently bhi 2 options rakhta hai. Toh hame $2 + 2$ nahi milta; hame $2$ branches milti hain, har ek phir $2$ mein split hoti hai → $2 \times 2 = 4$ complete outcomes.

MULTIPLY KYU KARTE HAIN AUR ADD NAHI? Yeh page ka sabse important idea hai, toh isko earn karte hain. "Add" sahi hota agar choices alternatives hote (A ya B karo). Lekin yahan choices stack hoti hain — tum A decide karte ho aur phir B decide karte ho. Har A-branch neeche B-choice ki ek poori copy carry karti hai. Copies-of-copies multiplication hai. Tree dekho: level 1 mein 2 nodes hain, level 2 mein per node $2$ children hain $= 4$ .

PICTURE. Ek branching tree. Red path chaar leaves mein se ek complete outcome trace karta hai (A=OUT, B=IN).

Step 3 — $n$ items mein se har ek ke 2 options → $2^{n}$ subset count

KYA HAI. Ab $n$ items karo, har ek ek independent IN/OUT switch. Multiplication rule mein plug in karo jahan har $m_{k} = 2$ hai: $item 1 2 \times item 2 2 \times \dots \times item n 2 = 2^{n}$

YEH "SUBSETS KI NUMBER" KE BARABAR KYU HAI? Ek subset exactly un elements ki choice hai jo IN hain. Toh "IN/OUT switches ki list" aur "subset" alag alag kapde pehne ek hi object hain. Switch-settings count karna hi subsets count karna hai — isliye $2^{n}$ subsets, parent note se exactly match karta hai.

PICTURE. Ek doubling staircase: 1 item → 2, 2 items → 4, 3 → 8, 4 → 16. Red curve flat black budget line ke upar uthti hai — jis moment woh cross karti hai woh moment hai jab brute force time out hone lagta hai.

Step 4 — Options-per-choice badlo: alphabet $b$ , length $k$ → $b^{k}$

KYA HAI. Multiplication rule rakho lekin har choice ke kitne options hain yeh badlo. $10$ digits par length $k$ ka ek PIN: $k$ slots mein se har ek ke $b = 10$ options hain. $slot 1 b \times slot 2 b \times \dots \times slot k b = b^{k}$

YEH $2^{n}$ KE SAME FORMULA KYU HAI? Kyunki $2^{n}$ bas $b^{k}$ tha jisme $b = 2$ , $k = n$ tha. Subsets 2-letter alphabet ("IN","OUT") par PINs hain. Ek rule, do costumes. 4-digit PIN ke liye, $1 0^{4} = 10000$ — chhota, isliye parent ka crack loop instantly khatam ho jaata hai. Isliye chhote PINs weak hote hain.

PICTURE. $k$ slots ki ek row, har ek ek red dial hai jisme $b$ ticks hain; caption unhe multiply karke dikhata hai.

Step 5 — Jab choices shrink karti hain: permutations se $n!$ milta hai

KYA HAI. Ab twist. $n$ distinct items ko $n$ ordered slots mein arrange karo. Slot 1: $n$ items mein se koi bhi. Lekin ek rakh diya, woh use ho gaya — slot 2 mein sirf $n - 1$ bache hain, slot 3 mein $n - 2$ hain, … last slot mein $1$ hai. Options har step mein ek kam hote jaate hain: $slot 1 n \times slot 2 (n - 1) \times \dots \times 2 \times last slot 1 = n!$

SHRINKING KYU? Kyunki reuse forbidden hai — tum same item do baar nahi rakh sakte. Step 4 se compare karo, jahan ek digit repeat ho sakta tha (same $b$ har slot). Repetition allowed → constant options → $b^{k}$ . Repetition forbidden → dwindling options → $n!$ . Exponential aur factorial ke beech sirf yahi fark hai ki pool refill hota hai ya nahi.

PICTURE. Slots ka ek funnel: pehle slot ko saare $n$ red tokens feed karte hain, baad ke har slot ko visibly chhota pool feed karta hai.

Step 6 — Unordered pairs: $n^{2}$ , phir half karo → $(2 n)$

KYA HAI. 2 items choose karo jahan order matter nahi karta. Do sub-steps. Pehle, ordered pairs: slot 1 = $n$ options, slot 2 = $n - 1$ (no reuse) → $n (n - 1)$ . Lekin $(A, B)$ aur $(B, A)$ same unordered pair hain, toh humne har cheez do baar count ki hai. 2 se divide karo: $double-count ko halve karo \frac{n ( n - 1 )}{2} = (2 n) = Θ (n^{2})$

EXACTLY 2 SE KYU DIVIDE KARTE HAIN? Kyunki 2 cheezein ke pair ko $2! = 2$ orders mein likha ja sakta hai, aur har unordered pair ordered count mein apne saare orderings mein dikhta hai. Do orderings ek mein collapse hoti hain → 2 se divide karo. Yahi exactly wajah hai ki parent ka Two-Sum loop for j in range(i+1, n) likhta hai — i+1 se start karna har unordered pair ko ek baar visit karta hai, yeh built-in halving hai.

PICTURE. $n \times n$ cells ka ek grid. Black diagonal (self-pairs $i = i$ , forbidden) crossed out hai; do triangles mirror images hain; sirf red upper triangle rakha jaata hai.

Step 7 — Degenerate aur edge cases (koi gap mat chhodo)

KYA HAI. Formulas weird inputs par survive karne chahiye. Har ek walk karo:

Input	Formula kya kehta hai	Meaning — kya yeh sane hai?
$n = 0$ subsets	$2^{0} = 1$	Haan: empty set kuch nahi ka ek subset hai.
$n = 0$ permutations	$0! = 1$	Haan: kuch nahi arrange karne ka exactly ek tarika hai (empty arrangement).
$n = 1$ pairs	$(2 1) = \frac{1 \cdot 0}{2} = 0$	Haan: tum 1 item se 2 distinct items nahi pick kar sakte.
$k = 0$ PIN	$b^{0} = 1$	Haan: empty string ek length-0 PIN hai.
$b = 1$ alphabet	$1^{k} = 1$	Haan: ek symbol ke saath, sirf ek string exist karti hai.

YEH CHECK KYU KARTE HAIN? Ek brute-force loop boundary par crash ya miss nahi karna chahiye. range(1 << 0) hai range(1) — yeh ek baar run karta hai, correctly empty subset enumerate karta hai. Agar tumhara formula wahaan $0$ deta, tumhara loop ek real candidate skip kar deta. Math aur loop edges par agree karte hain — yahi safety proof hai.

PICTURE. $n = 0, 1, 2$ ki ek number line jisme har count apni true value par land karta hai, aur $n = 0$ cases (jo logon ko surprise karte hain) red mein circled hain.

Recall

$0! = 1$ kyun hai aur $0$ kyun nahi? Items ke empty set ka ek arrangement ::: exactly ek hai — woh arrangement jo kuch nahi rakhti. Zero ways to fail ek valid (empty) outcome chhod deta hai. Yeh $n! = n \times (n - 1)!$ ko $n = 1$ par consistent bhi rakhta hai: $1! = 1 \times 0! = 1$ .

Ek-picture summary

Upar sab kuch ek hi rule hai — har step par options multiply karo — chaar tarike se moda gaya:

options 2 par constant → $2^{n}$ (subsets)
options $b$ par constant → $b^{k}$ (tuples/PINs)
options draining $n, n - 1, \dots, 1$ → $n!$ (permutations)
2 steps ke liye options drain, phir halve → $(2 n) = Θ (n^{2})$ (pairs)

Red curves ( $2^{n}$ , $n!$ ) almost immediately black $1 0^{8}$ budget line ke paar rocket kar jaati hain; black curves ( $n^{2}$ , $n lo g n$ ) crawl karti hain. Yahi gap poori wajah hai ki Dynamic Programming, Greedy Algorithms, aur NP-Hard Problems ke liye pruning exist karti hai.

Recall Feynman: plain words mein poora walkthrough

Brute force ko kitni cheezein try karni hain yeh count karna hamesha ek hi game hai: har step par, poochho "yeh step kitne ways mein ja sakta hai?" aur unhe multiply karo. Agar har step ek yes/no switch hai, tum 2's ka bunch multiply karte ho aur $2^{n}$ milta hai — woh har subset hai. Agar har step ek digit hai, tum 10's multiply karte ho aur $1 0^{k}$ milta hai — woh har PIN hai. Agar tum logon ko line up kar rahe ho aur kisi ko reuse nahi kar sakte, toh choices ki number har step mein shrink hoti hai — $n$ , phir $n - 1$ , phir $n - 2$ — aur unhe multiply karne par $n!$ milta hai. Agar tum sirf ek pair chahte ho aur order ki parwah nahi, unhe ordered count karo ( $n$ times $n - 1$ ) aur phir half kar do kyunki tumne har pair dono taraf se count ki. Scary part formulas nahi hain — yeh hai ki $2^{n}$ aur $n!$ itni fast shoot up karti hain ki $n = 20$ ya kuch ke baad, "sab kuch try karo" universe ki umar se zyada time leta. Yahi ek fact wajah hai ki hum kabhii zyada clever algorithms invent karne ki zyada koshish karte hain.