Backtracking — state-space tree, pruning: Question bank

3.7.16 · D5 · Coding › Algorithm Paradigms › Backtracking — state-space tree, pruning

True or false — justify

Backtracking hamesha optimal solution dhundh leta hai.

False — plain backtracking saare valid solutions ya pehla solution enumerate karta hai; isme "best" ka koi built-in notion nahi hota. Ek bound add karke best-so-far track karna use Branch-and-Bound bana deta hai.

Pruning se backtracking ke reported solutions badal jaate hain.

False — pruning sirf un branches ko remove karti hai jinmein provably koi valid leaf nahi hoti, isliye complete solutions ka reported set brute force jaisa hi rehta hai; sirf runtime differ karta hai.

Backtracking ki worst-case time complexity hamesha brute force se better hoti hai.

False — ek adversarial input har partial check satisfy kar sakta hai aur kuch bhi prune nahi karta, toh worst case

O (b^{d})

hi rehta hai; dekho Time-Complexity. Pruning sirf average case mein help karti hai.

State-space tree ke har node par ek complete solution hota hai.

False — sirf leaves complete solutions (ya dead-ends) hote hain; internal nodes partial solutions hain jo abhi construct ho rahe hain.

State-space tree search ke dauran physically memory mein exist karta hai.

False — ye implicit hota hai. DFS sirf current root-to-node path call stack par rakhta hai; tree on the fly generate hoti hai aur kabhi fully materialise nahi hoti.

Backtracking aur Depth-First-Search bilkul same algorithm hain.

False — backtracking ek implicit solution tree par DFS hai, lekin ye ek early feasibility prune aur ek explicit undo add karta hai taaki ek mutable state ko branches ke across reuse kiya ja sake.

Agar is_valid hamesha true ho, toh backtracking full brute-force enumeration mein degenerate ho jaata hai.

True — prune karne ko kuch na ho toh,

b^{d}

leaves mein se har ek visit hoti hai; algorithm phir bhi terminate karta hai lekin zero early-abandonment work karta hai.

Validity sirf leaf par check karna galat answers deta hai.

False — ye same answers deta hai, lekin pehle puri

b^{d}

tree generate karta hai, isliye ye correct toh hai lekin backtracking ka pura purpose defeat kar deta hai.

is_valid check ko pehle (tree mein upar) move karna kabhi correctness ko hurt nahi kar sakta.

True agar test monotonic ho — yaani agar partial state par ek violation future choices se "un-violated" nahi ho sakti; tab early pruning hamesha safe hai.

Spot the error

for c in candidates: state.add(c); backtrack(state) — kya missing hai?

Recursive call ke baad state.remove(c). Undo ke bina, shared mutable state sibling branches mein leak ho jaata hai aur baad ki har choice corrupt ho jaati hai.

Ek student subset-sum mein positive target ke saath if running_sum >= target prune karta hai. >= bug kyun hai?

Ye us branch ko cut karta hai jo exactly target hit karti hai, valid solutions discard ho jaate hain. Sahi prune > target hai, kyunki equality ek solution hai jo record karni chahiye, dead-end nahi.

Koi is_valid ko leaf par record ke andar rakhta hai aur claim karta hai ki ye prune karta hai. Ye kyun nahi karta?

Leaf par ek test tab run hota hai jab uske upar ki poori subtree already generate ho chuki hoti hai, isliye ye output filter karta hai lekin koi pruning nahi karta — koi subtree skip nahi ki gayi.

state.remove(c) ko backtrack(state) se pehle rakha gaya hai. Kya break hota hai?

Recursion tab ek aisi state explore karta hai jisme abhi-abhi ki gayi choice nahi hoti, isliye "explore" step galat partial solution dekhta hai — tumne explore karne se pehle hi undo kar diya.

Ek subset-sum solver mein negative numbers hain aur prune running_sum > target par hai. Ye unsafe kyun hai?

Negatives ke saath, ek bada sum baad mein target se neeche aa sakta hai, isliye sum > target ab permanent violation nahi hai — prune monotonic nahi hai aur valid subsets drop kar deta hai.

Do queens place ki gayi hain aur sirf column clash check kiya gaya, diagonals nahi. Kya symptom aata hai?

Invalid boards leaves tak survive kar jaate hain aur "solutions" ke roop mein record ho jaate hain; feasibility test incomplete hai, isliye pruning bahut kam fire hoti hai, zyada nahi.

Why questions

Ek node cut karna exponentially kitne dead-ends kyun khatam kar deta hai?

Ek invalid partial choice apni poori subtree ki har leaf ko poison kar deta hai; us subtree mein

b^{d - k}

tak leaves ho sakti hain, isliye uska root remove karna unhe ek baar mein eliminate kar deta hai.

Same state object ko har call mein fresh copy karne ki jagah undo kyun karna chahiye?

Ek mutable state reuse karna memory/speed optimisation hai; undo use parent ki exact configuration par restore karta hai taaki siblings bagair poori state clone kiye clean start kar sakein.

is_valid filter recursion ke andar, recursive call se pehle kyun likha jaata hai?

Taaki invalid choice ki poori subtree kabhi generate na ho. Recursion se pehle test karna hi pruning hai; baad mein test karna pehle generate karta hai phir discard karta hai.

Pruning Big-O unchanged kyun rakhti hai phir bhi real runtime slash kyun kar deti hai?

Big-O worst case measure karta hai, aur ek adversarial input kuch bhi prune nahi kar sakta; typical inputs early constraints violate karte hain, isliye zyaadatar branches root ke paas hi mar jaati hain, actual work huge factors se cut ho jaata hai.

"One queen per row" encoding "any queen anywhere" se smarter kyun hai?

Ye no-two-in-a-row constraint ko branching mein hi bake kar deta hai, branching factor shrink ho jaata hai aur invalid states ki poori ek class validity test hone se pehle hi remove ho jaati hai.

Backtracking breadth-first order ki jagah DFS kyun use karta hai?

DFS ek waqt mein ek root-to-leaf path follow karta hai, isliye sirf current partial solution aur uske ancestors stack par rehte hain —

O (d)

memory — jabki BFS partial solutions ka poora ek frontier store karta.

Edge cases

Ek problem jisme root par koi bhi candidate kabhi valid nahi — backtracking kya return karta hai?

Solutions ka empty set; root zero children expand karta hai, recursion turant unwind ho jaati hai, aur ye correctly "no solution exists" report karta hai.

Subset-sum with target = 0 aur all-positive elements — answer kya hai?

Empty subset

{}

, jiska sum 0 hai. Ek solver jo depth 0 par empty state record karna bhool jaata hai ye valid solution miss kar deta hai.

N-Queens with

n = 1

— kitne solutions?

Ek: single queen single square par, koi earlier rows nahi hain conflict karne ke liye, isliye validity test vacuously satisfied ho jaata hai.

N-Queens with

n = 2

n = 3

— kya hota hai?

Zero solutions; har placement kisi column ya diagonal par clash karta hai, isliye saari branches dead-ends tak prune ho jaati hain aur search empty return karta hai — ye correct result hai, bug nahi.

Depth 0 ka tree (state root par already complete hai) — backtrack kya karta hai?

is_complete turant true hota hai, isliye ye root record kar leta hai aur kabhi candidate loop mein ghuse bina return ho jaata hai.

Agar do alag decision orders same partial state produce karein, toh kya backtracking unhe deduplicate karta hai?

Nahi — plain backtracking unhe alag tree paths maanta hai aur duplicate solutions record kar sakta hai; deduping ke liye ek explicit visited-set ya choices ki canonical ordering chahiye (dekho Permutations-and-Combinations).

Connections

Parent topic — wo derivation jinhe ye traps stress-test karti hain.
Branch-and-Bound — backtracking kya ban jaata hai jab tum optimality bound add karo.
Dynamic-Programming — alternative jab overlapping subproblems (sirf constraints nahi) dominate karein.