DSA Sheet - Day 10 Recursion and Backtracking
🚀 DSA Sheet – Day 10: Recursion & Backtracking
This set strengthens your recursion fundamentals and introduces classic backtracking problems like Maze traversal and Subsets with duplicates.
📊 Progress Tracker
Progress: 0 / 5 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Knight's Tour | Solve | Medium | Google, Microsoft | |
| Subsets II | Solve | Medium | Apple, Meta | |
| Merge Sort | Solve | Easy | Amazon, Oracle | |
| Rat in a Maze | Solve | Medium | Amazon, Microsoft | |
| Count Inversions | Solve | Hard | Amazon |
🧠 Key Approaches
- Knight's Tour: Backtracking with 8 possible moves
- Subsets II: Backtracking + skip duplicates
- Merge Sort: Divide & conquer (recursive splitting)
- Rat in a Maze: DFS + path tracking
- Count Inversions: Merge sort based counting
⚡ Quick Cheatsheet
Subsets II (Handle Duplicates)
sort(nums.begin(), nums.end());
void solve(int i){
for(int j = i; j < n; j++){
if(j > i && nums[j] == nums[j - 1])
continue;
// pick nums[j]
solve(j + 1);
}
}
Merge Sort
void mergeSort(int l, int r){
if(l >= r) return;
int mid = (l + r) / 2;
mergeSort(l, mid);
mergeSort(mid + 1, r);
merge(l, mid, r);
}
Rat in a Maze (DFS)
void dfs(int i, int j){
if(i == n - 1 && j == n - 1){
// path found
return;
}
// explore 4 directions
}
🔥 Pro Tip
Recursion mastery comes from patterns:
- Divide & Conquer (Merge Sort)
- Backtracking (Subsets, Maze)
- Pruning unnecessary paths