Lesson 3 � Intermediate

Backtracking Framework

Backtracking recursion ka advanced version hai jismein hum "explore karke undo" karte hain. Brute force se better hai kyunki hum saari branches explore nahi karte � pruning se galat paths ko early reject karte hain. N-Queens, Sudoku, Maze � sab backtracking se solve hote hain.

? 30 min✓ Intermediate✓ Recursion patterns

Backtracking kya hai?

WHAT

Backtracking ek algorithmic technique hai jismein hum recursive tarike se solutions build karte hain. Agar current path galat hai toh peeche jaake (backtrack) undo karte hain aur doosra path try karte hain. Ye DFS tree traversal ki tarah hai with pruning.

WHEN

Jab multiple choices hon aur har choice ke baad naye choices generate hon, jab constraint satisfaction problem ho, jab saare valid solutions find karne hon, jab early termination possible ho � tab backtracking use karo.

WHERE

N-Queens, Sudoku Solver, Rat in Maze, Word Search, Combination Sum, Permutations, Graph Coloring, Hamiltonian Path � ye sab classic backtracking problems hain.

Mental Model: Imagine karo tum ek maze mein ho. Har junction pe 3 paths hain. Tum ek path pe chalte ho � agar dead end mil jaaye toh peeche aate ho aur doosra path try karte ho. Backtracking bhi yahi karta hai � explore, backtrack, try new path.

Choose ✓ Explore ✓ Unchoose Framework

Har backtracking problem mein ye 3 steps hote hain. Isko yaad rakhlo � 90% problems solve ho jayengi:

# Backtracking Framework Template
def backtrack(path, choices):
 # BASE CASE: End condition mila
 if end_condition:
 result.append(path[:]) # Valid solution mila!
 return
 
 # CHOICES: Har choice pe
 for choice in choices:
 # CHOOSE: Choice ko path mein daalo
 path.append(choice)
 
 # EXPLORE: Recursively aage badho
 backtrack(path, new_choices)
 
 # UNCHOOSE: Choice hatao (backtrack!)
 path.pop()

# Example: Generate all subsets
def subsets(nums):
 result = []
 
 def backtrack(start, current):
 result.append(current[:])
 for i in range(start, len(nums)):
 current.append(nums[i])
 backtrack(i + 1, current)
 current.pop() # UNCHOOSE
 
 backtrack(0, [])
 return result

Pruning: Backtracking ka sabse bada fayda hai pruning � galat paths ko early reject karna. Agar pata chal jaaye ki current path se valid solution nahi banega toh us branch ko explore mat karo. Time complexity bahut kam ho jaati hai.

Decision Tree with Pruning

Backtracking ka decision tree dekho � kaise pruning hoti hai:

# Decision Tree � Subsets with pruning
# nums = [1, 2, 3], target = 3

# []
# / \
# [1] []
# / \ / \
# [1,2] [1] [2] []
# / \ / \ / \ / \
# [1,2,3][1,2][1,3][1][2,3][2][3][]
#
# Pruning: Agar current_sum > target
# toh us branch ko mat explore karo!
# [1,2,3] = 6 > 3 ✓ PRUNE (skip this branch)

def subset_sum(nums, target):
 result = []
 nums.sort() # Sort for pruning
 
 def backtrack(start, current, current_sum):
 if current_sum == target:
 result.append(current[:])
 return
 if current_sum > target:
 return # PRUNE � aage mat jao
 
 for i in range(start, len(nums)):
 current.append(nums[i])
 backtrack(i + 1, current, current_sum + nums[i])
 current.pop()
 
 backtrack(0, [], 0)
 return result

Step-by-Step: Subset Sum Problem

Subset Sum ek classic backtracking problem hai. Given array aur target � subsets find karo jinka sum target ke barabar ho:

def subset_sum(nums, target):
 result = []
 nums.sort()
 
 def backtrack(start, path, remaining):
 if remaining == 0:
 result.append(path[:])
 return
 if remaining < 0:
 return # Prune
 
 for i in range(start, len(nums)):
 if i > start and nums[i] == nums[i-1]:
 continue # Skip duplicates
 path.append(nums[i])
 backtrack(i + 1, path, remaining - nums[i])
 path.pop() # Backtrack
 
 backtrack(0, [], target)
 return result

# Example
nums = [2, 3, 6, 7]
target = 7
print(subset_sum(nums, target)) # [[7], [2, 3, 2]] � wait, 2 is not there twice
# Correct output: [[7]] since 2+3=5, 2+6=8, 3+6=9, none equal 7
# Actually [7] is a subset that sums to 7

Generic Backtracking Template

# Template for all backtracking problems
def solve(problem_state):
 result = []
 
 def backtrack(state):
 if is_solution(state):
 result.append(extract_solution(state))
 return
 
 for choice in get_choices(state):
 if is_valid(choice, state): # Pruning condition
 make_choice(state, choice) # CHOOSE
 backtrack(state) # EXPLORE
 undo_choice(state, choice) # UNCHOOSE
 
 backtrack(problem_state)
 return result

Backtracking vs Brute Force

Brute Force

Saari possibilities explore karta hai � pruning nahi hoti. Time: O(2^n) ya O(n!). Har branch pe jaata hai chahe valid ho ya nahi.

Backtracking

Pruning ke saath explore karta hai. Agar pata chal jaaye ki current path se solution nahi banega toh us branch ko skip karta hai. Effective time kam hota hai.

Example

N-Queens mein brute force O(n^n) hai. Backtracking mein agar queen place karte waqt conflict ho toh us row/column ko skip karte hain � effective time O(n!) se bhi kam ho jaata hai.

Try it: code khud likho

Exercise

Question: Array [1, 2, 3, 4] mein subsets find karo jinka sum 5 ho. Kitne subsets hain✓ Sirf number daalo.

Question: Backtracking mein 3 steps ka naam kya hai✓ Comma-separated daalo (jaise "choose,explore,unchoose").

Common mistakes

Unchoose (backtrack) bhool jaana: path.pop() ya equivalent cleanup zaroor karo. Nahi toh galat state next iteration mein jaayegi.
Pruning na lagana: Agar constraint hai toh pehle check karo. Nahi toh brute force ban jayega � time complexity kharab ho jayegi.
Base case galat hona: Kabhi remaining == 0 (subset sum), kabhi len(path) == n (permutations), kabhi is_valid_board() (N-Queens). Problem ke hisaab se base case likho.
Sorting skip karna: Duplicates handle karne ke liye sorting zaroori hai. Bina sort ke duplicate solutions aayenge.
Pass by reference ki galti: path[:] ya path.copy() use karo result mein add karte waqt. Nahi toh reference saved rahega aur baad mein path change hone se result bhi change hoga.

Lesson complete?

Backtracking framework samajh aa gaya✓ Ab N-Queens problem dekhte hain � backtracking ka sabse famous application.