Brute force — exhaustive search, when acceptable: Worked examples

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

Scenario matrix

Har brute-force problem exactly ek search-space shape mein fit hoti hai, aur har shape ka ek size formula hota hai (sab parent note mein derive kiye gaye hain). Neeche ki matrix har case class list karti hai jo is topic mein aa sakti hai, aur batati hai ki konsa worked example use cover karta hai.

Cell	Search-space shape	Size formula	Danger case to cover	Example
A	Unordered pairs	$(2 n) = \frac{n ( n - 1 )}{2}$	double-counting $(i, j)$ vs $(j, i)$	Ex 1
B	Sab subsets	$2^{n}$	$n = 0$ → empty set case	Ex 2
C	Sab permutations	$n!$	kya $n$ itna chota hai?	Ex 3
D	$k$ -tuples over alphabet $b$	$b^{k}$	short code = weak	Ex 4
E	Feasibility limit (bahut slow?)	plug into $≲ 1 0^{8}$	brute force reject karo	Ex 5
F	Degenerate / empty input	size $= 1$ or $0$	koi valid answer exist nahi karta	Ex 6
G	Word problem (real world)	model then count	words → count mein translate karo	Ex 7
H	Exam trap (growth vs bound)	compare two formulas	"exponential = bad" myth	Ex 8

Danger case column ka yahi poora point hai: koi case tab tak covered nahi hai jab tak tune dikhaya nahi ki uski edge par kya hota hai.

Figure — Brute force — exhaustive search, when acceptable

Ex 1 — Cell A: unordered pairs (aur double-count edge)

Candidates count karo. Yeh step kyun? Brute force hamesha space ko size karke shuru hoti hai. Ek candidate = positions ki ek unordered pair. $n = 5$ ke saath yeh hai $(2 5) = \frac{5 \cdot 4}{2} = 10 pairs .$ $25$ nahi — kyunki $(i, j)$ aur $(j, i)$ ek hi pair hain, aur koi number khud se pair nahi kar sakta.
Bina double-counting ke enumerate karo. Yeh step kyun? Agar hum inner loop ko $0$ se chalayein toh hum har pair ko do baar visit karenge, aadha kaam waste hoga (aur possibly ek element ki khud se "pair" report hogi, distance $0$ , jo galat hai). Fix: inner loop i+1 se start karo.

def closest_pair(a):
    n = len(a); best = None
    for i in range(n):
        for j in range(i+1, n):     # j > i  -> distinct, no double count
            d = abs(a[i]-a[j])
            if best is None or d < best[0]:
                best = (d, i, j)
    return best

Closest region ko haath se run karo. Sorted values hain $1, 3, 5, 8, 11$ ; sabse tight gap $3$ aur $5$ ke beech hai (distance $2$ ), positions $2$ (value $5$ ) aur $4$ (value $3$ ) par. Baaki sab adjacent gaps bhi check karo ( $1 - 3 = 2$ bhi!) — check: $∣1 - 3∣ = 2$ bhi hai. Toh distance $2$ par do pairs hain; brute force loop order mein jo pehle milti hai wo return karta hai.

Verify: pairs ki sankhya $= (2 5) = 10$ . Sab pairs mein minimum distance $= 2$ ( ${1, 3}$ aur ${3, 5}$ se). ✔

Ex 2 — Cell B: sab subsets, empty set sameta

Count karo. Kyun? $3$ items mein se har ek independently andar ya bahar hai → $2^{3} = 8$ subsets. Aur yahan khaas baat: isme empty set bhi shamil hai (mask $= 0$ , sum $= 0$ ).
Bitmasks se enumerate karo. Bitmasks kyun? $0$ se $2^{n} - 1$ tak ek number mask mein har item ke liye ek bit hota hai; bit $i$ set ⇔ item $i$ choose kiya gaya. Yeh sabse clean tarika hai $2^{n}$ subsets ko exactly ek baar hit karne ka (dekho Bitmasking).

def has_subset_sum(vals, target):
    n = len(vals)
    for mask in range(1 << n):          # 0 .. 2^n - 1  (includes mask=0)
        s = sum(vals[i] for i in range(n) if mask & (1 << i))
        if s == target:
            return True
    return False

Winning mask haath se walk karo. Kyun? Hum answer dekhna chahte hain, sirf trust nahi karna. Mask $= 10 1_{2} = 5$ items $0$ aur $2$ select karta hai → values $2 + 7 = 9$ (nahi). Mask $= 01 1_{2} = 3$ items $0, 1$ select karta hai → $2 + 3 = 5$ ✔. Toh answer hai True.
$n = 0$ edge. Yeh kyun cover karein? Empty input naive code ko tod deta hai. Yahan $2^{0} = 1$ : loop ek baar mask=0 ke saath chalta hai, sum $= 0$ . Toh empty item list sirf target = 0 se match kar sakti hai.

Verify: subsets ki sankhya $= 2^{3} = 8$ . Subset ${2, 3}$ ka sum $5$ hai → answer True. Empty-list on target $0$ → True; on target $5$ → False. ✔

Ex 3 — Cell C: sab permutations (kya $n$ itna chota hai?)

Count karo. Kyun? Tour non-start cities ${1, 2, 3}$ ka ek permutation hai. Orderings ki sankhya $= 3! = 6$ . (Agar hum start fix karein, to sab $4$ ko permute karne se rotations over-count honge — city $0$ ko fix karne se yeh hat jata hai.)
Pehle feasibility check karo. Kyun? Permutation brute force sirf chhote $n$ ke liye safe hai. Rule of thumb: $n!$ ko $\sim 1 0^{8}$ se kam rehna chahiye. Yahan $3! = 6$ — trivially fine. $10$ cities ke liye $9! = 362880$ (abhi bhi theek hai); $14$ cities ke liye $13! \approx 6.2 \times 1 0^{9}$ — bahut slow, Dynamic Programming par switch karo (Held–Karp).

from itertools import permutations
def best_tour(cost):
    n = len(cost); best = None
    for perm in permutations(range(1, n)):   # (n-1)! orders
        route = [0] + list(perm) + [0]
        d = sum(cost[route[k]][route[k+1]] for k in range(len(route)-1))
        best = d if best is None else min(best, d)
    return best

Ek chote case ko haath se check karo. Maano costs hain $c_{01} = 1, c_{02} = 2, c_{03} = 3, c_{12} = 1, c_{13} = 5, c_{23} = 1$ . Route $0 \to 1 \to 2 \to 3 \to 0 = 1 + 1 + 1 + 3 = 6$ . Route $0 \to 2 \to 1 \to 3 \to 0 = 2 + 1 + 5 + 3 = 11$ . Sab $6$ mein best 6 hai.

Verify: tours ki sankhya $= (4 - 1)! = 6$ . Di gayi matrix ke liye minimum tour length $= 6$ . ✔

Ex 4 — Cell D: $k$ -tuples over an alphabet (short code = weak)

Tuples count karo. Kyun? $k = 3$ positions mein se har ek independently $b = 26$ symbols mein se ek pick karta hai → $b^{k} = 2 6^{3}$ candidates. $2 6^{3} = 17576.$ $1 0^{8}$ se kam, toh yeh instantly crack ho jata hai.
PIN se compare karo. Kyun? Yeh dekhne ke liye ki alphabet size aur length ka trade-off kya hai. $6$ -digit PIN hai $b = 10, k = 6$ : $1 0^{6} = 1, 000, 000$ . Toh $6$ -digit PIN mein actually $3$ -letter password se zyada candidates hain — length soochte se zyada matter karti hai.
Lesson kya hai. Kyun? Isi liye short codes weak hote hain (parent note, Ex 3): $b^{k}$ tabhi attacker-proof banta hai jab $k$ bada ho. $12$ lowercase letters dete hain $2 6^{12} \approx 9.5 \times 1 0^{16}$ — ab brute force fail hoti hai, jaisa hona chahiye.

Verify: $2 6^{3} = 17576$ ; $1 0^{6} = 1000000$ ; toh PIN space $1000000/17576$ factor se bada hai. ✔

Ex 5 — Cell E: feasibility limit (brute force reject karo)

Kaam estimate karo. Kyun? Parent ka feasibility test: $N = (space size) \times (verify cost)$ . Yahan $N = (2 n) \approx \frac{n ^{2}}{2} = \frac{( 1 0 ^{5} ) ^{2}}{2} = 5 \times 1 0^{9} .$
Line in the sand se compare karo. Kyun? $1 0^{8}$ ops/sec roughly ek second compute hota hai. $5 \times 1 0^{9} ≫ 1 0^{8}$ , toh brute force ko ~50 seconds chahiye — yeh time out hogi. Ise reject karo; hash set ( $O (n)$ ) ya sort + two pointers use karo (dekho Time Complexity & Big-O).
Boundary kahan hai? Kyun? Solve karo $\frac{n ^{2}}{2} = 1 0^{8} \Rightarrow n = 2 \times 1 0^{8} \approx 14142$ . Toh $Θ (n^{2})$ brute force $n \approx 1.4 \times 1 0^{4}$ tak theek hai aur $1 0^{5}$ se bahut pehle hopeless hai — parent ke table row " $n \leq 5000$ : maybe" se match karta hai.

Verify: $(2 1 0 ^{5}) \approx 5 \times 1 0^{9} > 1 0^{8}$ (reject). Break-even $n = 2 \cdot 1 0^{8} \approx 14142$ . ✔

Ex 6 — Cell F: degenerate / empty input (koi valid answer nahi)

Har ek ke liye candidates count karo. Kyun? Ek pair ke liye do distinct positions chahiye.
- (a) $n = 0$ : $(2 0) = 0$ pairs → loop body kabhi nahi chalta → None return karta hai.
- (b) $n = 1$ : $(2 1) = 0$ pairs → None bhi. Ek akela element khud se pair nahi kar sakta.
- (c) $n = 2$ : $(2 2) = 1$ pair → $3 + 4 = 7$ check karta hai ✔ → $(0, 1)$ return karta hai.
Yeh kyun matter karta hai. Kyun? Dangerous case hai $n \leq 1$ : naive code jo assume karta hai ki "hamesha ek pair hogi" wo crash ya garbage return karta hai. Sahi brute force simply zero candidates enumerate karta hai aur "no answer" report karta hai — jo correct behaviour hai.
General rule. Kyun? Empty enumeration ⇒ empty answer. Brute force degenerate inputs par automatically correct hoti hai jab tak tum galat tarike se special-case nahi karte.

Verify: $n = 0, 1, 2$ ke liye pairs $0, 0, 1$ hain; sirf case (c) succeed karta hai, indices $(0, 1)$ return karta hai jahan $3 + 4 = 7$ . ✔

Ex 7 — Cell G: ek real-world word problem

Ise tuples ki tarah model karo. Kyun? " $3$ types mein se at most $3$ coins" → hum counts $(c_{1}, c_{3}, c_{4})$ try karte hain jahan $c_{1} + c_{3} + c_{4} \leq 3$ ho.

def fewest_coins(target, coins=(1,3,4), cap=3):
    best = None
    for c1 in range(cap+1):
      for c3 in range(cap+1):
        for c4 in range(cap+1):
          if c1+c3+c4 <= cap:
            if 1*c1 + 3*c3 + 4*c4 == target:
              used = c1+c3+c4
              best = used if best is None else min(best, used)
    return best

Total $6$ ke liye search karo. Enumerate kyun? Arbitrary coin sets ke liye koi guaranteed greedy shortcut nahi hai (greedy fail kar sakta hai — dekho Greedy Algorithms). Brute force safe baseline hai. $6$ hit karne wale candidates: $3 + 3$ (do coins), ${1, 1, 4}$ (teen coins), ${1, 1, ...}$ ... Minimum 2 coins hai ( $3 + 3$ ).
Real-world caveat. Cap kyun? " $\leq 3$ coins" cap ke bina space infinite hoga, toh brute force ko ek bound chahiye. Unbounded change ke liye yeh Dynamic Programming problem ban jata hai.

Verify: $3 + 3 = 6$ using $2$ coins; koi single coin $6$ ke equal nahi, toh minimum $2$ hai. ✔

Ex 8 — Cell H: exam trap (growth rate vs input bound)

Bounds plug in karo. Kyun? Constraint ke bina Big-O ka matlab nahi. Actual operation counts compute karo: $2^{18} = 262144, (1 0^{5})^{2} = 1 0^{10} .$
Compare karo. Kyun? $2^{18} \approx 2.6 \times 1 0^{5}$ hai jo $1 0^{10}$ se ~38000 guna chota hai. Toh "exponential" P almost instantly khatam hoga jabki "polynomial" Q time out hogi. Exam ka claim galat hai.
Takeaway. Kyun? Growth rate algorithms ko ek hi input par $n \to \infty$ ke saath rank karta hai, alag bounds par nahi. Brute force discard karne se pehle hamesha given constraint substitute karo. Yahi parent note ki steel-man mistake hai.

Verify: $2^{18} = 262144 < 1 0^{10} = (1 0^{5})^{2}$ , toh P kam operations karta hai. ✔

Recall Konsa cell? (self-test)

"Sab pairs dhundo jo $t$ sum karte hain" — konsi shape? ::: Cell A, unordered pairs, $(2 n)$ . "Jobs ka har ordering try karo" — konsi shape? ::: Cell C, permutations, $n!$ . "Har subset jo knapsack mein fit ho" — konsi shape? ::: Cell B, subsets, $2^{n}$ . "Guess a PIN of length $k$ " — konsi shape? ::: Cell D, $k$ -tuples, $b^{k}$ . Break-even $n$ for $Θ (n^{2})$ under $1 0^{8}$ ops? ::: about $14142$ ( $2 \times 1 0^{8}$ ).

Dekho bhi: Backtracking (brute force jo dead branches ko pehle prune karta hai), NP-Hard Problems (jahan brute force + pruning aksar sabse zyada hai jo hum kar sakte hain), aur Hinglish version.