Brute force — exhaustive search, when acceptable: Foundations

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

Yeh page assume karta hai ki tumne pehle kuch nahi dekha. Neeche har symbol use hone se pehle earn kiya gaya hai. Yeh parent topic ke liye prerequisite floor hai, jo Algorithm Paradigms ke andar baithta hai.

0. Absolute-zero starting point: "candidate" kya hota hai?

Kisi bhi symbol se pehle, ek word: candidate. Candidate ek single possible answer hai jo tum hand in kar sakte ho — ek guess. Brute force woh act hai jisme tum tamam guesses ki complete list likhte ho aur har ek ko tick karte ho.

Figure — Brute force — exhaustive search, when acceptable

Figure dekho: har amber dot ek candidate hai; un sabko encircle karta cyan box search space hai. Brute force = har dot ko visit karo. Is page ka baaki sab kuch sirf yeh count karna hai ki common shapes ke problems mein kitne dots hote hain — kyunki woh count hi running time hai.

1. Symbol $n$ — "input kitna bada hai?"

$n$ ko ek row mein boxes ki number ki tarah picture karo:

 box 1   box 2   box 3   ...   box n
[     ] [     ] [     ]  ...  [     ]

Topic ko iske kyon zarurat hai: parent mein har cost formula $n$ ke terms mein likhi hai. Agar hum "input ka size" ko naam nahi de sakte, to hum yeh nahi keh sakte ki kaam kaise grow karta hai. $n$ woh dial hai jise hum ghumake poochte hain "agar input bada ho jaye to?"

2. Symbol $\leq$ — "at most"

Ek number line picture karo: $x \leq y$ ka matlab hai $x$ ya to $y$ par baitha hai ya uske left mein kahin bhi.

 <----|---------|---------|--------->
      x         y
      x is here or anywhere left of y

Topic ko iske kyon zarurat hai: constraints hamesha " $n \leq 20$ " (input size ki upper bound) ke roop mein phrase hote hain aur feasibility checks "weight $\leq W$ " (cap exceed nahi karna chahiye) ke roop mein. "Brute force kab acceptable hai?" ki poori table $\leq$ bounds ki list hai.

3. Multiplication as independent choices — counting engine

Brute force mein jo kuch bhi explosive hai woh EK idea se aata hai: jab tum ek ke baad ek kai choices karte ho aur har choice dusre se free ho, to options ki count multiply karte ho.

Topic ko iske kyon zarurat hai: $2^{n}$ , $n!$ , aur (baad mein) $b^{k}$ sab isi rule ko baar baar apply karna hai. Yeh ek picture master karo aur scary formulas obvious ho jaayengi. Ab hum har ek derive karte hain.

4. $2^{n}$ — subsets ki number

Pehle, do sub-symbols.

Ab derivation, WHAT/WHY/PICTURE:

WHAT karte hain: items ko ek ek karke walk karo, har baar in ya out choose karo.
WHY multiply karte hain: choices independent hain (item 1 chunna item 2 ko restrict nahi karta), to rule of product se multiply karte hain. $n$ items hain, har ek ke paas $2$ options hain: $n 2 \times 2 \times \dots \times 2 = 2^{n}$ .
WHAT IT LOOKS LIKE: ek branching tree jo har level par double hota hai.

Figure mein neeche leaves gino: $n = 3$ items ke liye $2^{3} = 8$ leaves hain — woh $8$ subsets hain, empty selection se lekar full tak.

5. $n!$ — orderings (permutations) ki number

WHAT karte hain: ordered slots left to right fill karo.
WHY numbers shrink karte hain: slot 1 mein $n$ items mein se koi bhi ja sakta hai. Place hone ke baad, slot 2 ke liye sirf $n - 1$ items bachte hain, phir $n - 2$ , aur aise hi. Choices phir bhi multiply sense mein independent hain (koi bhi first choice kisi bhi valid second choice ke saath pair ho sakti hai), to multiply karte hain: $n \times (n - 1) \times \dots \times 1 = n!$ .
WHAT IT LOOKS LIKE: wahi branching tree, lekin har level mein pichle se ek branch kam hoti hai.

6. $(2 n)$ — unordered pairs ki number

WHAT karte hain: pehla item pick karo ( $n$ ways) aur doosra, different item ( $n - 1$ ways): yeh $n (n - 1)$ ordered pairs deta hai.
WHY 2 se divide karte hain: har unordered pair do baar count hua (ek baar $(a, b)$ ke roop mein, ek baar $(b, a)$ ke roop mein). Double-count undo karo $2$ se divide karke: $(2 n) = \frac{n ( n - 1 )}{2}$
WHAT IT LOOKS LIKE: tamam $(i, j)$ cells ki ek grid; diagonal (self-pairs $i = i$ ) throw out, aur dono triangles mirror images hain — sirf ek rakhte hain.

Figure mein diagonal ke upar cyan cells woh pairs hain jo hum rakhte hain; greyed-out diagonal self-pairs hai, aur lower triangle woh duplicate hai jise divide away karte hain. Exactly isi liye parent ke Worked Example 1 mein inner loop i+1 se start hoti hai.

7. $b^{k}$ — $b$ symbols par length- $k$ strings ki number

Parent ka Example 3 ek PIN crack karta hai aur " $b^{k}$ " quote karta hai. $b$ aur $k$ ko zero se earn karte hain.

WHAT karte hain: $k$ ordered slots fill karo; har slot independently $b$ symbols mein se koi bhi hold kar sakta hai.
WHY $b^{k}$ hai: slot 1 mein $b$ options, slot 2 mein $b$ options, …, kul $k$ slots. Repeated independent choices → rule of product → $k b \times b \times \dots \times b = b^{k}$ . (Permutations ke unlike, symbols repeat ho sakte hain, isliye count $b - 1$ tak nahi shrink karta — har slot phir bhi sare $b$ options dekhta hai.)
WHAT IT LOOKS LIKE: subsets jaisi wahi branching tree, lekin ab har level $2$ ki jagah $b$ branches mein split hoti hai.

8. Big- $Θ$ aur Big- $O$ — "count kitni tezi se grow karti hai?"

Kyon constants throw away karte hain: hum care karte hain kaam kaise scale karta hai jab input badhta hai, exact tick-count nahi, jo tumhari machine par depend karta hai. $n$ double karne par $n^{2}$ algorithm $4 \times$ kaam karta hai — woh ratio useful truth hai.

Topic ko iske kyon zarurat hai: parent ki poori acceptability table ( $O (n!)$ , $O (2^{n})$ , $O (n^{2})$ …) is language mein likhi hai. $Θ$ / $O$ ke bina hum " $2^{n}$ at $n = 18$ " ko " $n^{2}$ at $n = 1 0^{5}$ " se compare nahi kar sakte.

9. Bits, AND operator, aur bit-masks — subset ko number mein turn karna

Parent ke Example 2 mein for mask in range(1 << n) loop hai aur mask & (1 << i) test hai. Ab decode karte hain.

$items (i_{2}, i_{1}, i_{0}) = (1, 0, 1) ⟶ binary 101 = 5 ⟶ subset {i_{0}, i_{2}}$

Test mask & (1 << i) number $1 ≪ i$ build karta hai (slot $i$ mein ek single $1$ ) aur use mask ke saath AND karta hai. Result non-zero tabhi hoga jab mask ka bit $i$ ek $1$ ho — yani yeh poochh raha hai "kya item $i$ is subset mein hai?". & us ek bit ko isolate karta hai aur baakon sab ignore karta hai. Yeh machinery Bitmasking mein fully explore ki gayi hai.

Prerequisite map

Sab kuch parent mein funnel ho jaata hai: counts search-space size batate hain, Big- $Θ$ /Big- $O$ batata hai kitni tezi se grow karta hai, aur $\leq$ constraints batate hain ki time budget mein fit hota hai ya nahi.

Yeh foundations aage kahaan le jaate hain

Ek baar search space count karne aate hain, to tum decide kar sakte ho ki brute force accept karo ya zyada smart paradigm reach karo — Dynamic Programming (overlapping sub-answers reuse karo), Greedy Algorithms (locally-best moves par commit karo), ya Backtracking (dead branches jaldi prune karo). Un problems ke liye jahan koi shortcut known nahi — NP-Hard Problems — pruning ke saath brute force aksar wahi sab hota hai jo hum kar sakte hain.

Equipment checklist

Self-test: right side cover karo, answer do, phir reveal karo.

n

kya represent karta hai?

Input ka size — problem tumhe kitni cheezein deti hai.

x \leq y

plain words mein padhte hain.

x

at most

y

hai" —

x

ya to

y

se chota hai ya equal hai.

Multiplication (product) rule state karo.

Agar step 1 mein

a

independent options aur step 2 mein

b

hain, to combined count

a \times b

hai.

n

-element set mein

2^{n}

subsets kyon hote hain?

Har item independently IN ya OUT hai —

2

choices,

n

baar, multiply karo:

2^{n}

2^{0}

kya hai aur kyon?

1

— zero items ke saath phir bhi exactly ek subset hai, empty selection.

Permutations

2^{n}

ki jagah

n!

kyon dete hain?

Slots shrinking options se fill hote hain —

n

phir

n - 1

phir

n - 2

… — kyunki use ho chuke items repeat nahi ho sakte.

0!

kya hai aur kyon?

1

— kuch bhi order karne ka exactly ek tarika hai (empty ordering).

(2 n) = n (n - 1) /2

kyun hai, divide-by-2 ke saath?

n (n - 1)

ordered pairs count karta hai; har unordered pair do baar count hua, isliye

2

se divide karo.

b

aur

k

kya mean karte hain, aur length-

k

strings kitni hoti hain?

b

= har slot mein symbols ki number,

k

= slots ki number; count hai

b^{k}

Θ (f)

aur

O (f)

mein kya fark hai?

Θ

= exactly $f$ jaisa grow karta hai;

O

f

se zyada fast nahi (upper bound) grow karta.

mask & (1 << i) kya test karta hai, aur & kya karta hai?

& do numbers ko bit by bit AND karta hai; test non-zero tabhi hota hai jab bit

i

set ho — yani item

i

subset mein hai.

1 ≪ n

kiske equal hai?

2^{n}

— ek

1

jiske baad

n

zero-bits hain.

Recall Quick numeric readiness

$2^{20} \approx ?$ ::: lagbhag $1 0^{6}$ (ek million).
$10! \approx ?$ ::: lagbhag $3.6 \times 1 0^{6}$ .
$(2 5) = ?$ ::: $10$ .
$1 0^{4} = ?$ (ek 4-digit PIN space) ::: $10000$ .