Arey bacho! Jaldi se class mein aa jao aur whiteboard par apna dhyan lagao.
Pichle chapter mein humne Recursion (Chapter 8) ko bilkul basic se lekar call stack ke internal mechanics tak completely decode kiya. Humne seekha ki kaise ek function khud ko call karke badi problem ko smaller, identical subproblems mein todta hai.
Lekin bacho, real-world development aur technical interviews mein humare saamne aisi problems aati hain jahan humein ek single answer nahi dhoondhna hota. Humein bola jata hai:
- "Symmetry ke saare combinations generate karo."
- "Mera rasta block ho gaya hai, dhoondho aur kaunse alternate paths se destination tak pahunch sakte hain."
- "Chessboard par Queens ko aise bethane ke saare tarike generate karo taaki koi kisi ko maare na."
Jab humein saare possible valid paths explore karne hon, ya kisi constraint (shart) ke mutabik decision-making karni ho, tab hum recursion par ek extra step lagate hain—aur usi powerful paradigm ko hum Backtracking kehte hain!
Kuch bache backtracking ke recursive branching se darrte hain, par mera waada hai: Aaj ki class ke baad tum dynamic decisions ke recursive structures ko dhang se visualize kar paoge, decision trees trace kar paoge, aur in-place state modifications ko cleanly execute kar paoge.
Fatafat apni pen aur copy nikal lo, aur shuru karte hain Chapter 9: Backtracking! 🚀
Imagine karo tum ek purani Bhulbhulaiya (Maze) ke andar khade ho aur tumhein bahar nikalne ka rasta dhoondhna hai.
[ Entrance ]
│
▼
[ Intersection A ]
/ │ \
/ │ \
[ Dead End B ] [ Dead End C ] [ Path D ]
🛑 🛑 │
(Backtrack!) (Backtrack!) ▼
[ Exit 🏆 ]
Tum chalna shuru karte ho aur ek dynamic crossing (Intersection A) par pahunche. Tumhare paas teen raste hain: Left, Middle, aur Right.
- Tumne Choice 1 li (Left) aur aage badhe. Kuch door chalte hi saamne ek deewar aa gayi—Dead End B!
- Ab tum kya deewar tod kar aage badhoge? Bilkul nahi! Tum wapas piche mudoge (Backtrack karoge) Intersection A tak.
- Tumne Choice 2 li (Middle) aur aage badhe. Phir se Dead End C mila! Tumne phir se use discard kiya aur wapas piche mud kar Intersection A par aaye.
- Tumne Choice 3 li (Right) aur aage badhe. Boom! Tumhein bahar nikalne ka rasta mil gaya (Exit)!
Yahi complete process Backtracking hai!
Backtracking ek aisi systematic search technique hai jo brute force ki tarah saare possible solutions explore karti hai, par jaise hi lagta hai ki koi raasta galat direction mein ja raha hai (constraint violate ho raha hai), toh woh aage ke faltu paths par time waste nahi karti. Woh wahin se piche mudti hai (Undo/Backtrack karti hai) aur dusra options try karti hai.
Aksar bache in dono terms ke beech confuse ho jate hain. Whiteboard par is table ko dhyan se dekho:
| Feature | Recursion (The Engine ⚙️) | Backtracking (The Strategy 🗺️) |
|---|---|---|
| Basic Definition | Ek programming mechanism jahan function khud ko recursively call karta hai. | Ek algorithmic paradigm jo recursion ko use karke choices explore karta hai aur galat paths ko abandon karta hai. |
| Operational Goal | Problem ko subproblems mein divide karke unhe solve karna. | Constraint satisfaction ke basis par pure search space ko systematically explore karna. |
| The "Undo" Step | Recursion automatic stack frames unwind karta hai par state ko manual restore nahi karna padta. | State ko explicitly mutate karke recursive call se return hote waqt restore/undo karna padta hai. |
Teacher's Golden Rule: Recursion ek gaadi ka engine hai jo use aage chalata hai. Backtracking us driver ka dimaag hai jo rasta block hone par gaadi ko reverse (backtrack) karke sahi raste par le jata hai.
Backtracking ka koi bhi question likhne se pehle tumhare dimaag mein teen cheezein bilkul saaf honi chahiye:
- Choice (Chunav): Har step par tumhare paas kaun-kaun se options available hain? (Jaise Left jana ya Right jana).
- State (Awastha): Abhi tak tumne kaun-kaun se options choose kar liye hain aur bachi hui problem kya hai? (Jaise abhi tak array mein kaunse elements push kiye hain).
- Decision Tree (Faislon Ka Ped): Tumhare choices aur states ka ek pictorial flowchart.
State: [] (Empty Subset)
/ \
Include 1 / \ Exclude 1
▼ ▼
State: State: []
/ \ / \
Include 2/ Excl2\ Incl2 / Excl2\
▼ ▼ ▼ ▼
[]
- Recursion Tree: Yeh dikhata hai ki functions calls kis sequence mein stack par badh rahi hain (jaise
fib(4) -> fib(3) -> fib(2)). - Decision Tree: Yeh problem ke state mutations aur choice points ko visually represent karta hai. Decision tree ke har node par ek partial state hoti hai, aur edges choice paths ko represent karte hain.
Bacho, dhyan se suno. Backtracking ke 95% codes isi basic template ko follow karte hain. Agar tumne is template ke flow ko samajh liya, toh tum Sudoku Solver se lekar N-Queens tak sab likh paoge!
function backtrack(state, choices, result) {
// Pillar 1: Base Case (Stop Condition)
if (isSolution(state)) {
result.push(clone(state)); // State reference copy bug se bacho!
return;
}
// Pillar 2: Explore Choices
for (let choice of choices) {
if (isValid(choice, state)) { // Pillar 3: Pruning/Constraint check
// 1. Choose: State ko modify karo
makeMove(choice, state);
// 2. Explore: Recursively agle level par jao
backtrack(state, choices, result);
// 3. Undo (Backtrack): State ko wapas normal karo!
undoMove(choice, state);
}
}
}Suno bacho, agar hum bina soche samjhe har possible choice ko explore karenge, toh computation space exponential ho jayega (jaise O(2^N) ya O(N!)).
Pruning (Katai-Chhantai) ka matlab hai: "Jaise hi humein pata chale ki kisi branch par aage badhne se kabhi bhi sahi answer nahi mil sakta, toh us branch ko aage explore kiye bina wahin par rok do (prune kar do)!"
Decision Node
/ │ \
/ │ \
Choice A Choice B Choice C
│ │ │
Valid? Valid? Valid?
Yes No ❌ Yes
│ │ │
Explore PRUNED! Explore
- Without Pruning: Hum galat paths par bhi dhoondhte rehte hain, jisse computations waste hoti hain.
- With Pruning: Hum invalid paths ko shuruaat mein hi
returntriggers se block kar dete hain, jisse program ki execution speed dramatically boost ho jati hai.
Bacho, JavaScript mein reference handling ko samajhna backtracking ke liye bohot zaroori hai. 99% bache yahin par galti karte hain aur unka array output hamesha empty ya duplicate values se bhara aata hai!
JavaScript mein primitives (numbers, strings) by value copy hote hain, par objects aur arrays by reference copy hote hain.
let state = []; // Ref to Heap memory block A
let result = [];
function recursiveStep(state) {
state.push(1); // Modifies Heap block A directly!
result.push(state); // Storing the REFERENCE of block A, not the values!
}Agar tum loop ke end mein result.push(state) karoge aur fir state.pop() kar doge, toh pata hai kya hoga? result array mein bache arrays bhi dynamically alter hokar empty ban jayenge! Kyunki tumne original memory address ka pointer store karwaya tha, actual values ka snapshot nahi!
Jab bhi base case hit ho, hamesha array ki copy (shallow or deep copy) banakar push karo:
result.push([...state]); // ES6 Spread operator creates a brand new snapshot!"Sir, agar array copy hi karna hai, toh hum har recursive step par naya array create karke call kyun nahi bhejte?"
Performance and memory efficiency bacho! Agar tum har step par [...state] copy karke call bhejoge, toh har level par O(N) time aur memory allocate hogi. Lekin agar tum same array par push aur pop karoge (In-place manipulation), toh auxiliary space strictly call-stack depth tak optimized rahegi.
Bacho, is distinction table ko dhyan se dimaag mein betha lo:
| Category | Order Matters? | Element Count Constraints | Key Code Mechanism | Standard Complexity |
|---|---|---|---|---|
| Subsets (Power Set) | No | Variable size (from 0 to N). | Binary choice: Har element ko ya toh include karo ya exclude. | O(2^N) |
| Combinations | No | Fixed size K. | startIndex progression se duplicate symmetric paths avoid kiya jata hai. |
O<=ft(\binom{N}{K}\right) |
| Permutations | Yes | Fixed size N. | visited tracker ya dynamic swaps se array ke saare alignments generate kiye jate hain. |
O(N!) |
🚀 Whiteboard bilkul clean hai dosto! Ab hum in questions ko step-by-step trace karenge. Pehle main tumse options poochunga, phir code likhunga!
- Problem Statement: Given an integer array
numsof unique elements, return all possible subsets (the power set). - Example:
nums =→ Output:[[],,,].
Bacho, dimaag ki bati jalao:
- Har level par choices kya hain? Element
nums[i]ko subset mein include karna ya na karna. - State kya hai?
currentIndexaur abhi tak bacha subsetcurrentSubset. - Backtracking kyun required hai? Taaki hum un combinations ko revert (pop) karke exclude choices par traverse kar sakein.
- Brute Force: Saare possible binary values of 2^N represent indices check karo.
- Search Space: Total subsets of size N are exactly 2^N.
- JavaScript Code (Simple & Standard Backtracking):
function subsets(nums) {
const result = [];
function backtrack(index, currentSubset) {
// Base Case: Reached the end of decisions array index bounds
if (index === nums.length) {
result.push([...currentSubset]); // 📸 Clone snapshot to avoid reference sharing bugs!
return;
}
// Choice 1: INCLUDE the current element
currentSubset.push(nums[index]); // Choose
backtrack(index + 1, currentSubset); // Explore
// Choice 2: EXCLUDE the current element (Pop/Undo move)
currentSubset.pop(); // Undo
backtrack(index + 1, currentSubset); // Explore bache components
}
backtrack(0, []);
return result;
}result.push([...currentSubset]): originalcurrentSubsetreference Heap block par change hone se protect karne ke liye cloning snap create ki jati hai.currentSubset.push()¤tSubset.pop(): Same array reference par element modifications cleanly dynamic constant time O(1) swaps se maintain hoti hain.
backtrack(0, [])
/ \
Push 1/ \ (Exclude 1)
▼ ▼
backtrack(1,) backtrack(1, [])
/ \ / \
Push 2/ Excl2\ Push 2/ Excl2\
▼ ▼ ▼ ▼
[]
- Time Complexity: O(N · 2^N) where 2^N is total subsets and N is the array copying cost at leaf nodes.
- Space Complexity: O(N) auxiliary recursion tree call stack space.
- Problem Statement: Given an array of distinct integers
candidatesand a target integertarget, return a list of all unique combinations where the chosen numbers sum totarget. You may return the combinations in any order. The same number may be chosen fromcandidatesan unlimited number of times. - Example:
candidates =, target = 7→ Output:[,].
- Choices kya hain? Current candidate element
candidates[i]ko pick karna (hum use baar-baar pick kar sakte hain) ya agle element par badhna. - State क्या है? Current search target,
currentIndexin candidates array, andcurrentCombinationlist. - Backtracking kyun? Jab picked value target se badi ho jaye, toh value undo karke alternate elements explore karne ke liye.
- Pruning Strategy: Agar current sum target ko cross kar jaye (i.e.
target < 0), toh aage explore karne ka koi matlab nahi hai. Instantly use backtrack (return) kar do!
function combinationSum(candidates, target) {
const result = [];
// Performance Optimization: Sort candidates to prune early
candidates.sort((a, b) => a - b);
function backtrack(startIndex, currentSum, combination) {
// Base Case: Exact match found!
if (currentSum === target) {
result.push([...combination]); // Snapshot
return;
}
for (let i = startIndex; i < candidates.length; i++) {
// ✂️ Pruning Check: If candidates[i] exceeds bacha target sum,
// since candidates are sorted, all subsequent values will also violate target sum!
if (currentSum + candidates[i] > target) {
break; // Early loop breakage! Pruning in action!
}
// Choose
combination.push(candidates[i]); //
// Explore: We pass 'i' as startIndex (not 'i+1') because we can reuse same element!
backtrack(i, currentSum + candidates[i], combination);
// Undo
combination.pop(); //
}
}
backtrack(0, 0, []);
return result;
} backtrack(0, sum=0)
/ \
Add 2 / \ Add 3
▼ ▼
backtrack(0, sum=2) backtrack(1, sum=3)
/ \ │
Add 2 / \ Add 3 │ Add 3
▼ ▼ ▼
(0, sum=4) (1, sum=5) (1, sum=6) ──► Add 3 -> sum=9 > 7 (PRUNED! ✂️)
/ \ │
Add 2 / \ Add 3 │ Add 3
▼ ▼ ▼
(0, sum=6) (0, sum=7) (1, sum=8) (PRUNED! ✂️)
│ 🏆
▼
(0, sum=8) (PRUNED! ✂️)
- Complexity: Time: O(2^M) (where M is the recursive call depth target/minimum candidate), Space: O(depth) auxiliary recursion call stack space.
- Problem Statement: Given
npairs of parentheses, write a function to generate all combinations of well-formed parentheses. - Example:
n = 2→ Output:["(())", "()()"].
- Choices kya hain? Ek level par ya toh opening parenthese
'('rakhein ya closing parenthese')'. - State kya hai? Number of
openparentheses placed so far, and number ofcloseparentheses. - Constraints (Pavitra Niyam 📜):
- Hum
'('tabhi add kar sakte hain jabopen < n. - Hum
')'tabhi add kar sakte hain jabclose < open(warna parentheses invalid unbalanced ho jayengi).
- Hum
function generateParenthesis(n) {
const result = [];
function backtrack(currentString, openCount, closeCount) {
// Base Case: Balanced parentheses string of length 2*n constructed
if (currentString.length === 2 * n) {
result.push(currentString); // Strings are immutable value copies, no cloning needed!
return;
}
// Choice 1: Add Opening Parenthesis
if (openCount < n) {
backtrack(currentString + "(", openCount + 1, closeCount); // Explore
}
// Choice 2: Add Closing Parenthesis (Only if it preserves balance rules!)
if (closeCount < openCount) {
backtrack(currentString + ")", openCount, closeCount + 1); // Explore
}
}
backtrack("", 0, 0);
return result;
}- Complexity: Time: O<=ft(\frac{4^n}{sqrt{n}}\right) (Catalan number growth sequence), Space: O(n) auxiliary stack depth.
- Problem Statement: Chessboard (size N × N) par N Queens ko is tarah place karo taaki koi bhi do Queens ek doosre par attack na kar sakein (same row, same column, ya diagonals par check block lock range na ho).
N-Queens Valid Placement (4x4 Board):
. Q . .
. . . Q
Q . . .
. . Q .
- Choices: Har row
rpar Queen ko kis colcpar bethaen? - Constraints Check: Queen bethane se pehle check karo ki kya col
c, primary diagonalr-c, ya secondary diagonalr+cpar koi dusri Queen pehle se toh nahi bethi?
Instead of running a O(N) validation scan loop at every block, we use Sets to track attacked columns and diagonals in O(1) lookups!
function solveNQueens(n) {
const result = [];
const board = Array.from({ length: n }, () => new Array(n).fill('.'));
// Attacked tracks for O(1) validations
const attackedCols = new Set();
const attackedDiag1 = new Set(); // primary diagonal: r - c is constant
const attackedDiag2 = new Set(); // secondary diagonal: r + c is constant
function backtrack(row) {
// Base Case: All Queens safely placed!
if (row === n) {
result.push(board.map(r => r.join(''))); // Record snapshot
return;
}
for (let col = 0; col < n; col++) {
const diag1Key = row - col;
const diag2Key = row + col;
// ✂️ Pruning Check: If coordinates are under attack, skip!
if (attackedCols.has(col) || attackedDiag1.has(diag1Key) || attackedDiag2.has(diag2Key)) {
continue;
}
// 1. Choose (Place Queen & update attacked tracks)
board[row][col] = 'Q';
attackedCols.add(col);
attackedDiag1.add(diag1Key);
attackedDiag2.add(diag2Key);
// 2. Explore
backtrack(row + 1);
// 3. Undo (Backtrack - Remove Queen & remove attacked tracks)
board[row][col] = '.';
attackedCols.delete(col);
attackedDiag1.delete(diag1Key);
attackedDiag2.delete(diag2Key);
}
}
backtrack(0);
return result;
}- Complexity: Time: O(N!) computations, Space: O(N^2) board size storage space.
- Problem Statement: Write a program to solve a Sudoku puzzle by filling the empty cells. A Sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
- Each of the digits
- Choices: Kisi empty cell
(r, c)par'1'se'9'tak kaunsa digit valid hai? - Pruning Check: Digit place karne se pehle check karo: row, col, aur relative
3x3grid bucket mein woh digit pehle se toh nahi hai?
function solveSudoku(board) {
function isValid(row, col, char) {
for (let i = 0; i < 9; i++) {
// Check row violation
if (board[row][i] === char) return false;
// Check column violation
if (board[i][col] === char) return false;
// Check 3x3 subgrid violation
let subRow = 3 * Math.floor(row / 3) + Math.floor(i / 3);
let subCol = 3 * Math.floor(col / 3) + (i % 3);
if (board[subRow][subCol] === char) return false;
}
return true;
}
function solve() {
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
if (board[r][c] === '.') { // Empty cell found
for (let val = 1; val <= 9; val++) {
let char = val.toString();
if (isValid(r, c, char)) {
// Choose
board[r][c] = char;
// Explore
if (solve()) return true; // Propagation logic!
// Undo
board[r][c] = '.';
}
}
return false; // Triggers backtracking from previous levels!
}
}
}
return true; // Puzzle completely solved!
}
solve();
}- Complexity: Time: O(9^{81}) worst-case theoretical bound, par pruning ke karan real-world execution within milliseconds ho jati hai. Space: O(81) stack frame size.
- Problem Statement: Given an M × N grid of characters
boardand a stringword, returntrueifwordexists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically adjacent). - Example:
board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "ABCCED"→ Output:true.
- Choices: Grid ke cell
(r, c)se Up, Down, Left, ya Right jana. - State: Current board coordinates
(r, c), and target letter index inword. - Pruning Check: Cell boundary se bahar na ho, cell ka letter current target letter se match kare, aur cell pehle se visited na ho!
Instead of allocating a separate visited matrix, we can temporarily mask the board character during recursive descent and restore it during backtracking backtracking steps!
function exist(board, word) {
const R = board.length;
const C = board.length;
function dfs(r, c, index) {
// Base Case: Complete word matched!
if (index === word.length) return true;
// Pruning boundaries & mismatch checks
if (r < 0 || r >= R || c < 0 || c >= C || board[r][c] !== word[index]) {
return false;
}
// 1. Choose: Temporarily mask the visited cell
const temp = board[r][c];
board[r][c] = '#'; // Attacked/visited state marker
// 2. Explore: Try all 4 adjacent directions
const directions = [, [0, -1],, [-1, 0]];
for (let [dr, dc] of directions) {
if (dfs(r + dr, c + dc, index + 1)) {
return true; // Match found propagation!
}
}
// 3. Undo (Backtrack): Restore original character
board[r][c] = temp;
return false;
}
// Try starting search from every cell in the grid
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}- Complexity: Time: O(M · N · 4^L) where L is word length, Space: O(L) recursion depth stack.
Coding interviews mein sahi algorithm paradigm choose karne ke liye is cheat-sheet ko hamesha yaad rakhna:
ALGORITHMIC DECISION TREE
│
┌─────────────────────────────┴─────────────────────────────┐
Need ALL possible solutions/paths? Need ONLY one optimal value (min/max)?
│ │
▼ (Yes) ▼ (Yes)
Is there constraint pruning? Overlapping subproblems?
├─ Yes ==> Backtracking (DFS) ├─ Yes ==> Dynamic Programming (DP)
└─ No ==> Brute Force (DFS/BFS) └─ No ==> Greedy Algorithm
| Paradigm | Operational Philosophy | How it handles state space | When it fails ❌ |
|---|---|---|---|
| Brute Force | Evaluates the entire search space to find solutions, guaranteeing correctness at high performance cost. | No pruning; visits every possible state recursively. | Input size N is large, leading to TLE. |
| Backtracking | Incrementally builds candidate solutions, pruning invalid branches immediately. | Prunes suboptimal branches using constraint validation sets. | When we only need one optimal scalar value and past subproblems overlap. |
| Dynamic Programming | Solves problems by storing solutions to overlapping subproblems in memory. | Memoizes or tabulates subproblem states to avoid duplicate work. | Subproblems do not overlap (each decision branch state is completely unique). |
Technical interviews mein safe side rehne ke liye, in bugs se hamesha bacho:
- Forgetting to Clone Reference State during push:
Writing
result.push(currentSubset)instead ofresult.push([...currentSubset]). This duplicates empty arrays as output! - Missing the "Undo" step (pop) in loops:
Modifying the array state within choice loops but failing to
pop()or revert back tracked variables. This corrupts states across sibling branches! - Infinite Recursion Stack Overflow:
Forgetting base case terminal conditions or failing to increment index progression pointers (e.g. calling
backtrack(index)instead ofbacktrack(index + 1)). - Pruning Too Late: Running constraints check after going deep into recursion, instead of verifying them early before triggering sub-calls (early pruning).
- State space exploration, choice trees, and backtrack logic.
- Difference between Decision Trees and Recursion Trees.
- Performance pruning techniques to trim down exponential complexities.
- JS reference type semantic mechanics during recursion.
- The Choose-Explore-Undo cycle using mutable state tracking.
- Constraint hashing set check optimization for N-Queens.
- In-place board character masking for Sudoku & Word Search grid traversals.
- Try Subsets on LeetCode 78 using our standard template.
- Solve Combination Sum with duplicates constraint variants.
- Complete Generate Parentheses (LeetCode 22).