Brute force — exhaustive search, when acceptable

3.7.1 · Coding › Algorithm Paradigms

WHAT is brute force?

Do ingredients:

Enumeration — ek tarika har candidate ko exactly ek baar list karne ka (e.g. saare subsets, saare permutations, saare pairs, ek range mein saare integers).
Verification — ek predicate jo check karta hai ki koi candidate answer hai ya nahi.

WHY does it work (and why is it slow)?

Kimat hai time. Cost hai:

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

Candidates ki sankhya usually combinatorially badhti hai. Chaliye famous waalon ko first principles se derive karte hain.

Toh total time hai e.g. $Θ (2^{n} \cdot verify)$ ek subset search ke liye. Yeh tezi se explode hota hai — yahi wajah hai ki humein eventually smarter paradigms chahiye (greedy, DP, divide-and-conquer).

Figure — Brute force — exhaustive search, when acceptable

WHEN is brute force acceptable?

Brute force accept karo jab koi bhi yeh conditions hold karti ho:

Chhota input bound. Agar constraints $n \leq 20$ subsets ke liye ( $2^{20} \approx 1 0^{6}$ ) ya $n \leq 10$ permutations ke liye ( $10! \approx 3.6 \times 1 0^{6}$ ) kehti hain, toh total budget mein fit ho jata hai (roughly $1 0^{8}$ simple operations per second).
Yeh ek one-off hai / performance-critical nahi hai. Run-once scripts, config-time computation.
Tumhe ek correct reference chahiye optimized solution ko test karne ke liye (differential testing).
Koi better algorithm known nahi hai (kuch NP-hard problems — tum pruning ke saath brute force karte ho).

Reject karo jab search space tumhara time budget exceed kare aur exploit karne layak structure ho.

Constraints mein pattern	Likely intended complexity	Brute force OK?
$n \leq 11$	$O (n!)$	haan (permutations)
$n \leq 20$ – $24$	$O (2^{n})$	haan (subsets)
$n \leq 500$	$O (n^{3})$	borderline
$n \leq 5000$	$O (n^{2})$	shayad
$n \leq 1 0^{5}$	$O (n lo g n)$	nahi
$n \leq 1 0^{9}$	$O (lo g n)$ / $O (1)$	nahi

Worked Example 1 — Two-Sum by brute force

Problem: array $a$ aur target $t$ diya gaya hai, indices $i < j$ dhundho jahan $a_{i} + a_{j} = t$ .

def two_sum_brute(a, t):
    n = len(a)
    for i in range(n):          # candidate first index
        for j in range(i+1, n): # candidate second index
            if a[i] + a[j] == t:
                return (i, j)
    return None

Nested loop kyun? Candidates unordered pairs hain; saare $(2 n)$ pairs enumerate karna poori space ko exactly ek baar cover karta hai (hum $j$ ko $i + 1$ se start karte hain duplicates aur self-pairs se bachne ke liye).
Correct kyun? Har valid pair koi $(i, j)$ hoga jahan $i < j$ , aur hum sab ko visit karte hain.
Cost: $Θ (n^{2})$ . $n \leq$ kuch hazaar ke liye acceptable; $n = 1 0^{5}$ ke liye hash set use karo ( $O (n)$ ).

Worked Example 2 — Subset sum (max value under a weight cap)

Problem: items ka ek subset chunno jo total value maximize kare jab total weight $\leq W$ ho.

def best_subset(weights, values, W):
    n = len(weights)
    best = 0
    for mask in range(1 << n):     # all 2^n subsets, encoded as bits
        wt = val = 0
        for i in range(n):
            if mask & (1 << i):    # is item i in this subset?
                wt  += weights[i]
                val += values[i]
        if wt <= W:
            best = max(best, val)
        # Why this step? we only update best for FEASIBLE subsets
    return best

1 << n masks kyun? Ek bitmask mask $0$ se $2^{n} - 1$ tak har subset enumerate karta hai: bit $i$ set ⇔ item $i$ chosen. Yeh us $2^{n}$ count ko realise karta hai jo humne derive kiya tha.
Correct kyun? Optimal subset koi na koi subset hai → woh masks mein se ek hai → usse consider kiya jata hai.
Cost: $Θ (2^{n} \cdot n)$ . $n \leq 20$ ke liye theek hai. Uske baad, DP pe switch karo ( $O (nW)$ ).

Worked Example 3 — Cracking a 4-digit PIN

def crack(check):                       # check(pin) -> True if correct
    for pin in range(10000):            # 10^4 candidates
        s = f"{pin:04d}"
        if check(s):
            return s

$1 0^{4}$ kyun? 10 digits pe length-4 string → $b^{k} = 1 0^{4}$ candidates. Bahut chhota, isliye brute force instant hai — yahi wajah hai ki chhote PINs weak hote hain.

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho tumhari ghar ki chaabi kho gayi aur tumhare paas ek bade ring par 200 chaabiyan hain. Brute force bas har ek chaabi ko ek ek karke try karna hai jab tak darwaza na khule. Tum zaroor andar aa jaoge eventually — yeh acchi baat hai. Buri baat yeh hai ki agar bahut saari chaabiyan hain toh bahut time lag sakta hai. Toh brute force tab accha hai jab keyring chhoti ho, aur tab bura idea hai jab woh bahut badi ho — us case mein tum sochna prefer karoge ki kaunsi chaabiyan sahi lag rahi hain (yahi smarter algorithms karte hain).

Flashcards

Brute-force algorithm ko kya define karta hai?

Solution space mein har candidate enumerate karo aur har ek ko test karo; koi shortcut/insight use nahi hota. Correct hai agar enumeration complete ho aur verifier correct ho.

Brute force guaranteed correct kyun hai?

Agar enumeration koi candidate miss nahi karta, toh sach mein answer unhi mein se ek hoga jo check kiye gaye.

Ek n-element set ke subsets ki sankhya aur kyun?

2^{n}

— har element independently andar ya bahar hai (2 choices, n baar).

n items ke permutations ki sankhya aur kyun?

n!

— slot 1 ke liye

n

choices, slot 2 ke liye

n - 1

, … 1 tak.

n items se unordered pairs ki sankhya?

(2 n) = n (n - 1) /2 = Θ (n^{2})

Brute force ki general time cost?

(#candidates) × (ek ko verify karne ki cost).

Compare karne ke liye rough operations-per-second budget?

1 0^{8}

(se

1 0^{9}

) simple ops/sec.

Agar constraint

n \leq 20

hai, toh kaunsa brute force OK hai?

Subset enumeration

O (2^{n})

kyunki

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

Agar constraint

n \leq 11

hai, toh kaunsa brute force OK hai?

Permutation enumeration

O (n!)

Bitmasks se saare subsets kaise enumerate karte hain?

mask ko 0 se

2^{n} - 1

tak loop karo; bit

i

set ⇔ item

i

included.

Brute force kab use NAHI karna chahiye?

Jab search-space × verify cost ≫

1 0^{8}

ho aur exploitable structure (sorting, hashing, DP, greedy) exist kare.

Pairs ke liye common enumeration bug aur fix?

Double counting/self-pairs; fix: inner loop ko i+1 se start karo.

Optimize karne ke baad bhi brute-force version kyun rakhna chahiye?

Fast algorithm ki differential/stress testing ke liye ek correct reference ke roop mein.

Connections

Algorithm Paradigms — brute force baseline paradigm hai
Time Complexity & Big-O — $2^{n}$ , $n!$ , $n^{2}$ growth kaise estimate karte hain
Dynamic Programming — exponential subset/sequence brute force ko polynomial DP se replace karta hai
Greedy Algorithms — exhaustive checking ki jagah ek single myopic choice leta hai
Backtracking — pruning ke saath brute force; provably-bad branches skip karta hai
Bitmasking — subsets enumerate karne ki standard technique
NP-Hard Problems — jahan brute force (pruning ke saath) kabhi kabhi sabse best hota hai jo hum jaante hain