Question bank — Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets

False — zero effective pruning ke saath (e.g. ek constraint jo leaf tak kabhi violate nahi hoti) yeh brute force mein degenerate ho jaata hai aur usi poore tree ko visit karta hai. Backtracking tabhi jeeatta hai jab valid check branches ko jaldi khatam karta hai.

True in effect — agar har call ko apna independent state mile toh share karne ke liye kuch nahi hai jo corrupt ho, isliye undo ki zaroorat nahi. Lekin copying time/memory lagti hai, aur mutate-and-restore bilkul yahi avoid karta hai; yahi trade-off hai jiske liye shared-state style exist karta hai.

True — pehli call un worlds ko explore karti hai jahan nums[i] skip kiya gaya; phir append un worlds ko banata hai jahan yeh liya gaya. Do calls decision tree mein node i ke do children hain.

False — yeh har surviving branch explore karta hai kyunki yeh sab solutions collect karta hai, lekin pruning fir bhi attacked squares ko turant discard karti hai, tree ko per-row $N^2$ brute force se ghatakar zyada se zyada $N$ viable columns per row tak laati hai.

False — yeh True ke saath short-circuit karta hai precisely kyunki hum ek solution chahte hain; boolean ek deep success ko baaki sab alternatives rokne deta hai instead of bekar search karte rehne ke.

False — yeh branch tab tak khatam ho chuki hai; reset element i ko sibling branches ke liye free karta hai (e.g. "2 pehle" ko baad mein element 1 rakhne ki permission honi chahiye).

True — yeh partial solutions ke tree par DFS hai, ek added valid test ke saath jo children ko prune karta hai aur ek un-choose ke saath jo wapas aate waqt shared state restore karta hai.

True but useless — tum karte ho path ko mutate har sibling aur har deeper call par, isliye practically saare stored references usi ek final (usually empty) list ki taraf point karte hain. "Copy store karo" rule isliye hai kyunki woh mutation unavoidable hai.

False — Branch-and-Bound ek numeric bound use karke prune karta hai objective par (branch ka best-possible cost) optimization problems ke liye; backtracking ek feasibility test use karke prune karta hai (kya yeh partial state koi constraint violate karta hai). Dono tree-search skeleton share karte hain lekin different pruning questions poochte hain.

board mutate hota rehta hai jaise search continue hoti hai, isliye har stored solution baad mein usi state ki taraf point karti hai (aksar empty board). Tumhe ek deep snapshot store karna hoga, e.g. [''.join(row) for row in board].

Yeh pruning bahut late hai — tum already ek doomed placement ke poore subtree ko explore kar chuke ho, jo sirf brute force hai. Validity check pehle apply se honi chahiye taaki dead branches upar hi mar jayein.

Anti-diagonal (↗) miss ho jaati hai, isliye do queens jahan r1 + c1 == r2 + c2 slip through karke ek doosre par attack karti hain. Dono diagonals track karni hain: r - c ↘ ke liye aur r + c ↗ ke liye.

Value path se nikal jaati hai lekin used mark rahti hai, isliye element i baad ki branches ke liye permanently unavailable ho jaata hai — tum truncated, missing permutations paaoge. choose mein har mutation ka mirror un-choose mein hona chahiye.

Solutions box constraint violate karengi. Box test board[(b//3)*3 + i//3][(b%3)*3 + i%3] bhi run hona chahiye, jahan b = (r//3)*3 + c//3.

Pop ke bina, path elements accumulate karta rehta hai, isliye parent node par wapas aane par state polluted hai aur sibling subsets galat nikalti hain. Un-choose path ko wahi restore karta hai jo parent expect karta hai.

Tum tab ek mutation undo karte ho jo kabhi hui hi nahi (ek column remove karna jo kabhi add nahi hua), sets corrupt ho jaate hain ya error aata hai. Un-choose apply ke saath usi block ke andar hona chahiye, one-to-one pair karte hue.

Exactly ek queen per row fix karna row ko free choice se hata deta hai: har row ke liye hum sirf ek column choose karte hain ($N$ options), aur row conflicts structurally impossible ho jaate hain instead of kuch jise test karna padhe.

Down-right ek step chalane par r aur c dono mein 1 add hota hai, isliye unka difference r - c us diagonal par kabhi nahi badalta. Ek constant poori line identify karta hai, conflict test $O(1)$ banaata hai.

Sudoku ek single solution chahta hai, isliye boolean signal karta hai "mila — ruko". N-Queens har solution chahta hai, isliye short-circuit karne ke liye kuch nahi hai; yeh sab branches explore karta hai aur results ek shared list mein accumulate karta hai.

Har recursive frame automatically yaad rakhta hai "main kahan tha aur aage kya try karna hai"; jab ek branch marr jaati hai aur call return hoti hai, the stack caller ki position free mein restore kar deta hai — exactly wahi "last fork par wapas chalo" behavior.

Doomed configurations ki sankhya combinatorially badhti hai (8 queens ke liye billions). Depth 2 par ek branch marna har ek descendant ko skip karta hai jo woh generate karta — isliye pruning kaam ki growth rate badalta hai, na sirf ek constant factor.

Dono variables ko values assign karte hain (queen columns / cell digits) "all-different" constraints ke subject to rows, columns, diagonals ya boxes par; backtracking ek satisfying assignment ke liye standard systematic search hai.

DP overlapping subproblems ke answers reuse karta hai, lekin yahan hume har distinct subset/permutation emit karni hai — reuse karne ke liye kuch nahi hai aur koi shared optimal value nahi hai; har leaf ek unique required output hai.

Produce karne ke liye $n!$ leaves hain aur har ek ko result mein copy karne mein $O(n)$ lagta hai; used prune sirf invalid repeats hataata hai, valid orderings nahi, isliye real solutions ki count — aur is tarah kaam ka floor — unchanged rehta hai.

[[]] — ek list jisme single empty subset hai. Base case i == len(nums) turant ek empty path ke saath fire hota hai, correctly $2^0=1$ subset deta hai.

[[]] — ek permutation, empty ordering, kyunki $0!=1$. len(path) == len(nums) turant true ho jaata hai.

Dono ke liye zero. Search correctly run hoti hai, har attempt prune ho jaata hai, aur empty list return hoti hai — ek valid answer jiska matlab hai "koi arrangement exist nahi karta", bug nahi.

Exactly ek solution: akele square par ek queen, koi conflicts possible nahi. Loop use place karta hai aur r == n base case use record karta hai.

bt() koi '.' nahi paata, return True par pahunch jaata hai, aur board ko waise hi chhod deta hai — already-complete grid ko sahi tarah se solved report karta hai bina kuch touch kiye.

Kisi empty cell par har digit ok fail karta hai, har level False return karta hai, aur recursion poori tarah unwind ho jaati hai board ko original state mein chhod kar — solver simply tree exhaust karta hai aur no solution report karta hai.

Plain templates positions ko distinct maante hain, isliye duplicate values duplicate outputs produce karti hain (e.g. [1,1] repeated permutations deta hai). Unhe hatane ke liye extra sort-and-skip rule chahiye — base template apne aap dedupe nahi karta.