We want all solutions. Start from "what is a solution?" — a sequence of choices
c1,c2,…,cn. To enumerate all sequences we naturally recurse:
def backtrack(state): if is_complete(state): record(state) return for choice in candidates(state): if is_valid(state, choice): # <-- PRUNE here, before going deeper state.add(choice) # make the move backtrack(state) # explore state.remove(choice) # UNDO = backtrack
Complexity (forecast-then-verify): without pruning, the tree has up to bd nodes
(branching b, depth d). Pruning cannot improve the worst case (an adversarial input may
prune nothing) but slashes the average case dramatically. So Big-O stays O(bd); real
runtime plummets.
Imagine a maze of doors. You walk forward opening one door at a time. The moment a hallway
hits a wall, you don't keep wandering — you walk back to the last door and try a different
one. Smart bit: if you see a sign saying "no exit this whole wing", you skip the entire wing
instead of checking every room. That sign-reading is pruning; the walking back is
backtracking.
A tree whose root is the empty partial solution, edges are individual decisions, nodes are partial solutions, and leaves are complete solutions or dead-ends; explored via DFS.
In backtracking, what does "pruning" mean?
Refusing to expand a non-promising node — cutting its entire subtree — because the partial solution already violates a constraint.
Why must is_valid be checked BEFORE recursing, not at the leaf?
So invalid partial choices' whole subtrees are never generated, turning brute force into early-abandon search.
What three operations form the backtracking loop body?
Make the move (add), recurse (explore), undo the move (remove/backtrack).
Why is the "undo" step essential?
A single mutable state is shared across all branches; without undo, sibling/parent states get corrupted.
Does pruning improve worst-case Big-O?
No — an adversarial input may prune nothing, leaving O(b^d). It improves average/typical runtime only.
N-Queens: validity test for placing queen at row r, col c?
For every earlier row i<r: c != col[i] (column) AND |r-i| != |c-col[i]| (diagonal).
Difference between plain DFS and backtracking?
Backtracking is DFS over an implicit solution tree plus an early feasibility prune and explicit state undo to reuse one state.
What is a "promising/feasible" node?
A partial solution that could still be extended into a valid complete solution.
In subset-sum, what is a good pruning rule?
If running_sum > target, stop expanding — adding more elements can only increase the sum.
Backtracking ka basic idea simple hai: solution ko ek-ek decision karke banao, aur jaise hi koi
partial choice galat lage, turant us poore branch ko chhod do (prune karo) aur peeche ja kar dusra
option try karo (backtrack). Saari possible decision-sequences milke ek tree banati hain jise
state-space tree kehte hain — root pe khaali solution, har edge ek decision, aur leaves pe complete
solutions. Hum is tree ko DFS se ghoomte hain.
Asli magic pruning mein hai. Maan lo tum N-Queens solve kar rahe ho aur row 0 mein queen rakhi.
Ab row 1 mein agar koi column same column ya same diagonal pe aata hai, to wahin reject karo —
us choice ke neeche ka poora subtree explore karne ki zaroorat hi nahi. Isse exponentially saare
dead-ends ek hi jhatke mein cut ho jaate hain. Yaad rakho: validity check recurse karne se pehle
karna hai, leaf pe nahi — warna pura brute-force tree ban jayega aur fayda zero.
Ek important baat: har "move add karo" ke baad recursion khatam hone par "move undo karo" zaroori hai,
kyunki ek hi state object saare branches share karte hain. Add aur remove ka symmetry tootta hai to
siblings ka data corrupt ho jata hai — ye sabse common bug hai. Aur yaad rakho, pruning worst-case
Big-O ko improve nahi karta (adversarial input pe kuch prune hi nahi hoga, O(bd) hi rahega), par
real-life average case mein speed bahut zyada badha deta hai. Mantra: Choose → Explore → Un-choose,
aur jo promising nahi uska branch kaat do.
