RECURSION MASTER NOTES

Hinglish Sir-Style | Approach + Equations + C++ Templates + LeetCode Pattern Map

How to use these notes

Pehle question ko normal language me samjho, fir pattern pe map karo, fir template lagao. Recursion me magic nahi hota: ek function ka meaning pakdo, base
case lagao, smaller problem call karo, aur return/undo ka dhyan rakho. Ye notes exact paid-course copy nahi hain, but same DSA recursion ecosystem ko original
teacher-style me cover karte hain.

0. Recursion ka Big Picture

Recursion = function khud ko call karta hai to solve a smaller version of the same problem. Har recursive solution me 3 cheezein hoti hain:
function meaning, base case, recurrence relation.
Word Meaning in Hinglish Why important
Base case Jahan answer directly pata hai Infinite calls se bachata hai
Recursive case Badi problem ko chhoti problem me todna Core logic yahi hai
Call stack Function calls ka memory stack Dry run samajhne ka engine
Backtracking Try karo, call karo, undo karo Permutations, combinations, grid, N-Queens
Recurrence T(n) ya answer ko smaller answers me likhna Complexity aur logic dono clear

Sir Tip
Recursion likhne se pehle ye sentence bolo: solve(i, ...) ka matlab kya hai? Agar function ka meaning clear nahi hai, code jungle ban jayega.

1. Universal Recursion Formula

returnType solve(state) {
if (base condition) return base answer;

// choose / work before call if needed

answer = solve(smaller_state);
// work after call if needed

return answer;
}

Mathematical form: F(n) = combine(current work, F(n-1)) with F(0) known. For branching: F(i) = F(choice1) + F(choice2) + ...

2. How to Dry Run Recursion

1. Call ko stack me push karo. Example: fun(3) -> fun(2) -> fun(1) -> fun(0).
2. Base case hit hote hi return start hota hai.
3. Jo work recursive call se pehle hai wo going down me hoga.
4. Jo work recursive call ke baad hai wo coming back me hoga.
5. Multiple calls me recursion tree banao, stack se zyada tree helpful hota hai.

3. Basic Linear Recursion

3.1 Print N to 1
Question samjho
Input n diya hai. 5 ke liye 5 4 3 2 1 print karna hai. Bas decreasing order me numbers chahiye.

Approach Hinglish
Print before recursive call. Pehle current number ka kaam, fir smaller problem n-1.

Equation / Recurrence
print(n) = output n then print(n-1); base: n == 0

void printNto1(int n) {
if (n == 0) return;
cout << n << " ";

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 printNto1(n - 1);
}

Complexity + Tips
Time O(n), stack O(n).
Work before call means output going down.

3.2 Print 1 to N
Question samjho
Input n diya hai. 5 ke liye 1 2 3 4 5 print karna hai.

Approach Hinglish
Pehle smaller numbers print karao, fir current n print karo.

Equation / Recurrence
print(n) = print(n-1) then output n; base: n == 0

void print1toN(int n) {
if (n == 0) return;
print1toN(n - 1);
cout << n << " ";
}

Complexity + Tips
Time O(n), stack O(n).
Work after call means output returning time pe.

3.3 Sum of First N Numbers

Question samjho
n diya hai. 1 se n tak sum find karna hai. Example n=5 answer 15.

Approach Hinglish
sum(n) ka meaning: first n numbers ka sum. Current n + remaining n-1 ka sum.

Equation / Recurrence
S(n) = n + S(n-1), S(0)=0

int sumN(int n) {
if (n == 0) return 0;
return n + sumN(n - 1);
}

Complexity + Tips
Time O(n), stack O(n).
Formula direct n*(n+1)/2 bhi hai, but recursion concept ke liye relation important hai.

3.4 Factorial
Question samjho
n! n se 1 tak multiplication hai. Example 5! = 120.

Approach Hinglish
fact(n) ka meaning: n factorial. Current n multiply with factorial of n-1.

Equation / Recurrence
F(n) = n * F(n-1), F(0)=1

long long fact(int n) {

if (n == 0) return 1;
return 1LL * n * fact(n - 1);
}

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 Complexity + Tips
Time O(n), stack O(n).
Use long long. Factorial fast overflow karta hai.

3.5 Fibonacci
Question samjho
Nth Fibonacci nikalna hai jahan 0,1,1,2,3,5... sequence hoti hai.

Approach Hinglish
fib(n) depends on previous two terms. Ye branching recursion ka first example hai.

Equation / Recurrence
F(n)=F(n-1)+F(n-2), F(0)=0, F(1)=1

int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}

Complexity + Tips
Time O(2^n), stack O(n).
Repeated calls hoti hain. Later DP/memoization lagti hai.

4. Tail Recursion, Head Recursion, Tree Recursion

Type Shape Example Use
Tail recursion Last operation is recursive call print N to 1 Can be converted to loop
Head recursion Recursive call first print 1 to N Work happens while returning
Tree recursion Multiple recursive calls Fibonacci Recursion tree needed
Backtracking recursion Choose-call-undo Permutations Search all possibilities

Equation cheat
Linear recursion: T(n)=T(n-1)+O(1) -> O(n). Tree binary recursion: T(n)=2T(n-1)+O(1) approx O(2^n). Divide recursion: T(n)=T(n/2)+O(1) -> O(log n), and
T(n)=2T(n/2)+O(n) -> O(n log n).

5. Numbers and Math Recursion

5.1 Power x^n Basic
Question samjho
x aur n diye hain. x ko n times multiply karna hai.

Approach Hinglish
x^n = x * x^(n-1).

Equation / Recurrence
P(x,n)=x*P(x,n-1), P(x,0)=1

long long power(long long x, int n) {

if (n == 0) return 1;
return x * power(x, n - 1);
}

Complexity + Tips
Time O(n), stack O(n).

5.2 Fast Power / Binary Exponentiation

Question samjho
x^n efficient nikalna hai. n bahut bada ho sakta hai.

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 Approach Hinglish
n ko half karo. Agar n even hai to half*half. Agar odd hai to x*half*half.

Equation / Recurrence
P(n)=P(n/2)^2 if even; x*P(n/2)^2 if odd; base n=0

long long fastPow(long long x, long long n) {

if (n == 0) return 1;
long long half = fastPow(x, n / 2);
if (n % 2 == 0) return half * half;
return x * half * half;
}

Complexity + Tips
Time O(log n), stack O(log n).
LeetCode Pow(x,n) me negative n and INT_MIN handle karna hota hai.

5.3 LeetCode 50 Pow(x,n)

Question samjho
double x aur integer n. x raised to n return karna hai. n negative bhi ho sakta hai.

Approach Hinglish
n ko long long me lo kyunki INT_MIN ka abs overflow kar sakta hai. Agar n negative hai to answer = 1 / pow(x, -n).

Equation / Recurrence
pow(x,n): n<0 -> 1/pow(x,-n)

double myPow(double x, int n) {

long long N = n;
if (N < 0) {
x = 1.0 / x;
N = -N;
}
function<double(double,long long)> solve = [&](double a, long long b) -> double {
if (b == 0) return 1.0;
double half = solve(a, b / 2);
return (b % 2 == 0) ? half * half : a * half * half;
};
return solve(x, N);
}

Complexity + Tips
Time O(log n), stack O(log n).
Most common bug: n = -2147483648.

5.4 Count Digits

Question samjho
Number n me kitne digits hain. Example 259 -> 3.

Approach Hinglish
Every call n/10 karte jao. Har removed digit ke liye +1.

Equation / Recurrence
C(n)=1+C(n/10), base n<10 -> 1

int countDigits(int n) {
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}

Complexity + Tips
Time O(log10 n), stack O(log10 n).

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 0 ke liye answer 1 hota hai.

5.5 Sum of Digits

Question samjho
Number ke digits ka sum. 253 -> 10.

Approach Hinglish
Last digit n%10 add karo, remaining n/10 pe recursion.

Equation / Recurrence
S(n)=n%10 + S(n/10), S(0)=0

int sumDigits(int n) {
if (n == 0) return 0;
return n % 10 + sumDigits(n / 10);
}

Complexity + Tips
Time O(digits), stack O(digits).

5.6 Digital Root / Add Digits

Question samjho
Digits add karte raho jab tak single digit na ban jaye.

Approach Hinglish
Recursive version: sumDigits(n), if <10 return, else repeat. Math version faster hai.

Equation / Recurrence
DR(n)=DR(sumDigits(n)); base n<10

int addDigitsRec(int n) {
if (n < 10) return n;
int s = 0, x = n;
while (x) { s += x % 10; x /= 10; }
return addDigitsRec(s);
}

Complexity + Tips
Time O(log n repeated), stack small.
Math: n==0 ? 0 : 1 + (n-1)%9.

6. Arrays Using Recursion

6.1 Check if Array is Sorted
Question samjho
Array diya hai. Check karna hai increasing/non-decreasing sorted hai ya nahi.

Approach Hinglish
At index i, bas arr[i] <= arr[i+1] check karo and rest array sorted hai ya nahi.

Equation / Recurrence
sorted(i)=arr[i]<=arr[i+1] AND sorted(i+1)

bool isSorted(vector<int>& a, int i) {

if (i >= (int)[Link]() - 1) return true;
return a[i] <= a[i + 1] && isSorted(a, i + 1);
}

Complexity + Tips
Time O(n), stack O(n).

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

6.2 Linear Search Recursive
Question samjho
Array me target find karna hai. Milne par index return, warna -1.

Approach Hinglish
Current index check karo. Nahi mila to i+1 se search.

Equation / Recurrence
search(i)=i if a[i]==target else search(i+1)

int linearSearch(vector<int>& a, int i, int target) {

if (i == (int)[Link]()) return -1;
if (a[i] == target) return i;
return linearSearch(a, i + 1, target);
}

Complexity + Tips
Time O(n), stack O(n).

6.3 Binary Search Recursive

Question samjho
Sorted array me target find karna hai.

Approach Hinglish
Middle compare karo. Target chhota hai to left half, bada hai to right half.

Equation / Recurrence
T(n)=T(n/2)+O(1)

int binarySearch(vector<int>& a, int l, int r, int target) {

if (l > r) return -1;
int mid = l + (r - l) / 2;
if (a[mid] == target) return mid;
if (target < a[mid]) return binarySearch(a, l, mid - 1, target);
return binarySearch(a, mid + 1, r, target);
}

Complexity + Tips
Time O(log n), stack O(log n).
Overflow-safe mid use karo.

6.4 Reverse Array Recursively

Question samjho
Array ko reverse karna hai without loop.

Approach Hinglish
Two pointers l and r. Swap, then inner part reverse.

Equation / Recurrence
rev(l,r): swap a[l],a[r] + rev(l+1,r-1)

void reverseArray(vector<int>& a, int l, int r) {

if (l >= r) return;
swap(a[l], a[r]);
reverseArray(a, l + 1, r - 1);
}

Complexity + Tips
Time O(n), stack O(n).

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

6.5 Sum of Array
Question samjho
Array elements ka sum.

Approach Hinglish
Index i se end tak ka sum = a[i] + sum(i+1).

Equation / Recurrence
S(i)=a[i]+S(i+1), S(n)=0

int arraySum(vector<int>& a, int i) {

if (i == (int)[Link]()) return 0;
return a[i] + arraySum(a, i + 1);
}

Complexity + Tips
Time O(n), stack O(n).

7. Strings Using Recursion

7.1 Palindrome String
Question samjho
String same forward and backward hai ya nahi. Example madam true, hello false.

Approach Hinglish
Left and right characters compare karo. Agar equal hain to inner substring check karo.

Equation / Recurrence
pal(l,r)=s[l]==s[r] AND pal(l+1,r-1)

bool isPalindrome(string& s, int l, int r) {

if (l >= r) return true;
if (s[l] != s[r]) return false;
return isPalindrome(s, l + 1, r - 1);
}

Complexity + Tips
Time O(n), stack O(n).

7.2 Reverse String

Question samjho
String characters reverse karne hain.

Approach Hinglish
Two pointers swap, then move inward.

Equation / Recurrence
rev(l,r): swap + rev(l+1,r-1)

void reverseString(vector<char>& s, int l, int r) {

if (l >= r) return;
swap(s[l], s[r]);
reverseString(s, l + 1, r - 1);
}

Complexity + Tips
Time O(n), stack O(n).

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

7.3 Remove All Occurrences of a Character
Question samjho
String se ek character remove karna hai.

Approach Hinglish
Index wise build karo. Agar current char unwanted hai to skip, else add.

Equation / Recurrence
ans(i)=skip/take current + ans(i+1)

string removeChar(string& s, int i, char ch) {

if (i == (int)[Link]()) return "";
string rest = removeChar(s, i + 1, ch);
if (s[i] == ch) return rest;
return string(1, s[i]) + rest;
}

Complexity + Tips
Time O(n^2) due to string copy, stack O(n).
Better use reference output string for O(n).

7.4 Generate All Subsequences of String

Question samjho
String ke all subsequences print karne hain. Subsequence means order same, characters choose/skip kar sakte ho.

Approach Hinglish
Har character ke liye 2 choices: include or exclude.

Equation / Recurrence
F(i)=F(i+1 without s[i]) + F(i+1 with s[i])

void subseq(string& s, int i, string curr) {

if (i == (int)[Link]()) {
cout << curr << "\n";
return;
}
subseq(s, i + 1, curr); // exclude
subseq(s, i + 1, curr + s[i]); // include
}

Complexity + Tips
Time O(2^n * n), stack O(n).
Subsequence problems = include/exclude bell bajao.

8. Include / Exclude Pattern

Pattern definition
At every element, you either take it or ignore it. This creates 2^n possibilities. Ye pattern subsets, subsequences, subset sum, combination sum, target sum,
partition problems me repeatedly aata hai.

void solve(int i, vector<int>& nums, vector<int>& curr) {

if (i == [Link]()) {
// process curr
return;
}
// exclude
solve(i + 1, nums, curr);

// include
curr.push_back(nums[i]);
solve(i + 1, nums, curr);

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 curr.pop_back(); // undo
}

8.1 LeetCode 78 Subsets

Question samjho
Array nums diya hai. All possible subsets return karne hain. Order usually matter nahi karta.

Approach Hinglish
Har element ke liye exclude/include. Base pe current subset answer me push.

Equation / Recurrence
Total subsets = 2^n

class Solution {
public:
vector<vector<int>> ans;
void solve(int i, vector<int>& nums, vector<int>& cur) {
if (i == [Link]()) {
ans.push_back(cur);
return;
}
solve(i + 1, nums, cur); // not take
cur.push_back(nums[i]); // take
solve(i + 1, nums, cur);
cur.pop_back(); // backtrack
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> cur;
solve(0, nums, cur);
return ans;
}
};

Complexity + Tips
Time O(n*2^n), stack O(n), answer space O(n*2^n).
Question samjho: subset me order same nahi, bas collection chahiye.

8.2 LeetCode 90 Subsets II

Question samjho
Array me duplicates hain. Unique subsets chahiye.

Approach Hinglish
Sort karo. At each recursion level same value repeat choose mat karo.

Equation / Recurrence
Skip duplicates when i > start and nums[i]==nums[i-1]

class Solution {
public:
vector<vector<int>> ans;
void dfs(int start, vector<int>& nums, vector<int>& cur) {
ans.push_back(cur);
for (int i = start; i < [Link](); i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
cur.push_back(nums[i]);
dfs(i + 1, nums, cur);
cur.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort([Link](), [Link]());
vector<int> cur;
dfs(0, nums, cur);

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 return ans;
}
};

Complexity + Tips
Time O(n*2^n), stack O(n).
Duplicate handling ka mantra: sort + same level duplicate skip.

8.3 Count Subsets With Given Sum

Question samjho
Array and target sum diya hai. Kitne subsets ka sum target ke equal hai.

Approach Hinglish
Current element ko lo ya mat lo. Sum reduce karte jao.

Equation / Recurrence
count(i,sum)=count(i+1,sum)+count(i+1,sum-a[i])

int countSubsets(vector<int>& a, int i, int sum) {

if (i == [Link]()) return sum == 0;
int notTake = countSubsets(a, i + 1, sum);
int take = countSubsets(a, i + 1, sum - a[i]);
return take + notTake;
}

Complexity + Tips
Time O(2^n), stack O(n).
DP me same state (i,sum) memoize hoga.

8.4 LeetCode 494 Target Sum

Question samjho
Nums ke aage + ya - sign lagakar target banana hai. Count ways return.

Approach Hinglish
Each number ke liye two choices: plus or minus.

Equation / Recurrence
ways(i,sum)=ways(i+1,sum+a[i])+ways(i+1,sum-a[i])

class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
unordered_map<string,int> memo;
function<int(int,int)> dfs = [&](int i, int sum) -> int {
if (i == [Link]()) return sum == target;
string key = to_string(i) + "," + to_string(sum);
if ([Link](key)) return memo[key];
return memo[key] = dfs(i + 1, sum + nums[i]) + dfs(i + 1, sum - nums[i]);
};
return dfs(0, 0);
}
};

Complexity + Tips
Without memo O(2^n), with memo O(n*range).
Pure recursion se TLE aa sakta hai, but recursion thinking yahi hai.

9. Combination Pattern
Question feel
Combination me usually elements ka order output me matter nahi karta. [2,3] and [3,2] same combination hote hain. Isliye recursion me start index maintain
karte hain, taaki peeche na jao.

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

9.1 LeetCode 39 Combination Sum
Question samjho
Candidates and target diya hai. Same number unlimited times use kar sakte hain. Unique combinations chahiye.

Approach Hinglish
At index i, ya current number repeatedly lo, ya next index pe jao. Reuse allowed, so take ke baad i same rahega.

Equation / Recurrence
take: solve(i,target-a[i]); skip: solve(i+1,target)

class Solution {
public:
vector<vector<int>> ans;
void dfs(int i, vector<int>& cand, int target, vector<int>& cur) {
if (target == 0) { ans.push_back(cur); return; }
if (i == [Link]() || target < 0) return;

cur.push_back(cand[i]);
dfs(i, cand, target - cand[i], cur); // reuse same
cur.pop_back();

dfs(i + 1, cand, target, cur); // skip

}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> cur;
dfs(0, candidates, target, cur);
return ans;
}
};

Complexity + Tips
Exponential, stack O(target/min).
Reuse allowed means index same after take.

9.2 LeetCode 40 Combination Sum II

Question samjho
Candidates me duplicates hain. Har element only once use kar sakte hain. Unique combinations chahiye.

Approach Hinglish
Sort karo. For-loop recursion use karo. Same level duplicate skip. Next call i+1 because each element once.

Equation / Recurrence
dfs(start,target), choose i from start..n-1

class Solution {
public:
vector<vector<int>> ans;
void dfs(int start, vector<int>& a, int target, vector<int>& cur) {
if (target == 0) { ans.push_back(cur); return; }
for (int i = start; i < [Link](); i++) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > target) break;
cur.push_back(a[i]);
dfs(i + 1, a, target - a[i], cur);
cur.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort([Link](), [Link]());
vector<int> cur;
dfs(0, candidates, target, cur);

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 return ans;
}
};

Complexity + Tips
Exponential, stack O(n).
Same level duplicate skip is the crown jewel here.

9.3 LeetCode 216 Combination Sum III

Question samjho
1 se 9 tak numbers use karke exactly k numbers ka sum n banana hai. Har number once.

Approach Hinglish
Start index, remaining k, remaining sum. Choose next increasing number.

Equation / Recurrence
dfs(start,kLeft,sumLeft)

class Solution {
public:
vector<vector<int>> ans;
void dfs(int start, int k, int target, vector<int>& cur) {
if (k == 0 && target == 0) { ans.push_back(cur); return; }
if (k == 0 || target < 0) return;
for (int x = start; x <= 9; x++) {
cur.push_back(x);
dfs(x + 1, k - 1, target - x, cur);
cur.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> cur;
dfs(1, k, n, cur);
return ans;
}
};

Complexity + Tips
Small bounded search.
Question me exactly k numbers word important hai.

9.4 LeetCode 77 Combinations

Question samjho
n and k diye hain. 1..n me se k numbers ke all combinations return.

Approach Hinglish
For-loop with start. Choose number, then move to next.

Equation / Recurrence
dfs(start), stop when [Link]()==k

class Solution {
public:
vector<vector<int>> ans;
void dfs(int start, int n, int k, vector<int>& cur) {
if ([Link]() == k) { ans.push_back(cur); return; }
for (int x = start; x <= n; x++) {
cur.push_back(x);
dfs(x + 1, n, k, cur);
cur.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 vector<int> cur;
dfs(1, n, k, cur);
return ans;
}
};

Complexity + Tips
O(k*C(n,k)), stack O(k).
Pruning: remaining numbers insufficient ho to loop early stop.

10. Permutation Pattern

Permutation feel
Permutation me order matters. [1,2,3] and [2,1,3] different hain. Usually visited array ya swap-index method use hota hai.

10.1 LeetCode 46 Permutations

Question samjho
Distinct nums diye hain. All possible orderings return karni hain.

Approach Hinglish
At every position, any unused number choose karo.

Equation / Recurrence
n choices then n-1 then ... = n!

class Solution {
public:
vector<vector<int>> ans;
void dfs(vector<int>& nums, vector<int>& cur, vector<int>& used) {
if ([Link]() == [Link]()) { ans.push_back(cur); return; }
for (int i = 0; i < [Link](); i++) {
if (used[i]) continue;
used[i] = 1;
cur.push_back(nums[i]);
dfs(nums, cur, used);
cur.pop_back();
used[i] = 0;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> cur, used([Link](), 0);
dfs(nums, cur, used);
return ans;
}
};

Complexity + Tips
Time O(n*n!), stack O(n).
Use visited when input array should stay unchanged.

10.2 Permutations by Swapping

Question samjho
Same permutation but no visited array.

Approach Hinglish
Index pos decide karta hai kis place pe kaunsa number fix hoga. Swap each candidate into pos.

Equation / Recurrence
perm(pos): swap pos with i, perm(pos+1), undo

void permuteSwap(vector<int>& a, int pos, vector<vector<int>>& ans) {

if (pos == [Link]()) { ans.push_back(a); return; }

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 for (int i = pos; i < [Link](); i++) {
swap(a[pos], a[i]);
permuteSwap(a, pos + 1, ans);
swap(a[pos], a[i]); // undo
}
}

Complexity + Tips
Time O(n*n!), stack O(n).
Second swap compulsory. Warna array polluted ho jayega.

10.3 LeetCode 47 Permutations II

Question samjho
Nums me duplicates hain. Unique permutations chahiye.

Approach Hinglish
Sort + used array. Same value duplicate tab skip karo jab previous same unused ho.

Equation / Recurrence
if i>0 && nums[i]==nums[i-1] && !used[i-1] skip

class Solution {
public:
vector<vector<int>> ans;
void dfs(vector<int>& nums, vector<int>& cur, vector<int>& used) {
if ([Link]() == [Link]()) { ans.push_back(cur); return; }
for (int i = 0; i < [Link](); i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
used[i] = 1;
cur.push_back(nums[i]);
dfs(nums, cur, used);
cur.pop_back();
used[i] = 0;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort([Link](), [Link]());
vector<int> cur, used([Link](), 0);
dfs(nums, cur, used);
return ans;
}
};

Complexity + Tips
Time O(n*n!), stack O(n).
Duplicate permutations me ye condition gold hai.

10.4 LeetCode 784 Letter Case Permutation

Question samjho
String me letters ka case change karke all strings banani hain. Digits same rahenge.

Approach Hinglish
Character letter hai to lower/upper two choices. Digit hai to one choice.

Equation / Recurrence
F(i)=two calls for alphabet, one call for digit

class Solution {
public:
vector<string> ans;
void dfs(string& s, int i) {
if (i == [Link]()) { ans.push_back(s); return; }

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 if (isdigit(s[i])) {
dfs(s, i + 1);
} else {
s[i] = tolower(s[i]);
dfs(s, i + 1);
s[i] = toupper(s[i]);
dfs(s, i + 1);
}
}
vector<string> letterCasePermutation(string s) {
dfs(s, 0);
return ans;
}
};

Complexity + Tips
Time O(2^letters * n), stack O(n).

11. Backtracking on Strings

11.1 LeetCode 17 Letter Combinations of Phone Number
Question samjho
Digits 2-9 diye hain. Phone keypad letters ke all combinations return karne hain.

Approach Hinglish
Har digit ke possible letters pe loop. One letter choose, next digit solve.

Equation / Recurrence
branching product of letters per digit

class Solution {
public:
vector<string> ans;
vector<string> mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void dfs(string& digits, int i, string& cur) {
if (i == [Link]()) { ans.push_back(cur); return; }
for (char ch : mp[digits[i] - '0']) {
cur.push_back(ch);
dfs(digits, i + 1, cur);
cur.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if ([Link]()) return {};
string cur;
dfs(digits, 0, cur);
return ans;
}
};

Complexity + Tips
Time O(4^n*n), stack O(n).
Question keypad hai, so mapping first write karo.

11.2 LeetCode 22 Generate Parentheses

Question samjho
n pairs parentheses ke all valid strings banane hain.

Approach Hinglish
Open bracket tab tak laga sakte ho jab open < n. Close tab laga sakte ho jab close < open.

Equation / Recurrence
valid condition: close <= open <= n

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 class Solution {
public:
vector<string> ans;
void dfs(int open, int close, int n, string& cur) {
if ([Link]() == 2 * n) { ans.push_back(cur); return; }
if (open < n) {
cur.push_back('(');
dfs(open + 1, close, n, cur);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
dfs(open, close + 1, n, cur);
cur.pop_back();
}
}
vector<string> generateParenthesis(int n) {
string cur;
dfs(0, 0, n, cur);
return ans;
}
};

Complexity + Tips
Catalan count, stack O(n).
Close bracket kabhi open se zyada nahi hone dena.

11.3 LeetCode 131 Palindrome Partitioning

Question samjho
String ko aise parts me todna hai ki har part palindrome ho. All partitions return.

Approach Hinglish
Start index se end tak substring choose karo. Agar palindrome hai to choose and solve remaining.

Equation / Recurrence
dfs(start), choose s[start..end] if palindrome

class Solution {
public:
vector<vector<string>> ans;
bool pal(string& s, int l, int r) {
while (l < r) if (s[l++] != s[r--]) return false;
return true;
}
void dfs(int start, string& s, vector<string>& cur) {
if (start == [Link]()) { ans.push_back(cur); return; }
for (int end = start; end < [Link](); end++) {
if (pal(s, start, end)) {
cur.push_back([Link](start, end - start + 1));
dfs(end + 1, s, cur);
cur.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<string> cur;
dfs(0, s, cur);
return ans;
}
};

Complexity + Tips
Time approx O(n*2^n), stack O(n).

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 Partitioning question = cut points choose karne hote hain.

11.4 LeetCode 93 Restore IP Addresses

Question samjho
String digits diya hai. Valid IP addresses banane hain with 4 parts, each 0..255, no leading zero except single 0.

Approach Hinglish
At each part choose length 1,2,3. Validate part.

Equation / Recurrence
dfs(index, partsUsed)

class Solution {
public:
vector<string> ans;
bool valid(string part) {
if ([Link]() > 1 && part[0] == '0') return false;
int val = stoi(part);
return val <= 255;
}
void dfs(string& s, int idx, vector<string>& parts) {
if ([Link]() == 4) {
if (idx == [Link]()) ans.push_back(parts[0]+"."+parts[1]+"."+parts[2]+"."+parts[3]);
return;
}
for (int len = 1; len <= 3 && idx + len <= [Link](); len++) {
string part = [Link](idx, len);
if (!valid(part)) continue;
parts.push_back(part);
dfs(s, idx + len, parts);
parts.pop_back();
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> parts;
dfs(s, 0, parts);
return ans;
}
};

Complexity + Tips
Constant-ish bounded search.
Question samjho: IP exactly 4 blocks. Extra/missing digits invalid.

12. Grid and Matrix Backtracking

12.1 Rat in a Maze
Question samjho
n*n grid me 1 open and 0 blocked. Source se destination tak paths.

Approach Hinglish
Move allowed directions me jao. Visited mark karo, recursive call, then unmark.

Equation / Recurrence
dfs(r,c), stop at destination

void dfs(int r, int c, vector<vector<int>>& maze, vector<vector<int>>& vis, string& path, vector<string>& ans) {
int n = [Link]();
if (r == n - 1 && c == n - 1) { ans.push_back(path); return; }
string dir = "DLRU";
int dr[4] = {1,0,0,-1};
int dc[4] = {0,-1,1,0};

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr>=0 && nc>=0 && nr<n && nc<n && maze[nr][nc] && !vis[nr][nc]) {
vis[nr][nc] = 1;
path.push_back(dir[k]);
dfs(nr, nc, maze, vis, path, ans);
path.pop_back();
vis[nr][nc] = 0;
}
}
}

Complexity + Tips
Worst exponential.
Visited zaroori, warna loop me phas sakte ho.

12.2 LeetCode 79 Word Search

Question samjho
Board me adjacent cells se word banana hai. Same cell twice use nahi kar sakte.

Approach Hinglish
Har cell se DFS start karo. Current char match hona chahiye. Temporarily visited mark karo.

Equation / Recurrence
dfs(r,c,idx), idx==[Link] true

class Solution {
public:
bool dfs(vector<vector<char>>& b, string& w, int r, int c, int idx) {
if (idx == [Link]()) return true;
int m = [Link](), n = b[0].size();
if (r<0 || c<0 || r>=m || c>=n || b[r][c] != w[idx]) return false;
char old = b[r][c];
b[r][c] = '#';
bool ok = dfs(b,w,r+1,c,idx+1) || dfs(b,w,r-1,c,idx+1) || dfs(b,w,r,c+1,idx+1) || dfs(b,w,r,c-1,idx+1);
b[r][c] = old;
return ok;
}
bool exist(vector<vector<char>>& board, string word) {
for (int r=0;r<[Link]();r++)
for (int c=0;c<board[0].size();c++)
if (dfs(board, word, r, c, 0)) return true;
return false;
}
};

Complexity + Tips
Time O(m*n*4^L), stack O(L).
Use board cell as visited marker to save space.

12.3 LeetCode 200 Number of Islands

Question samjho
Grid me 1 land, 0 water. Connected land groups count karne hain.

Approach Hinglish
Jab unvisited land mile, count++ and DFS se pura island sink/visit kar do.

Equation / Recurrence
DFS visits each cell once

class Solution {
public:
void dfs(vector<vector<char>>& g, int r, int c) {

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 int m=[Link](), n=g[0].size();
if (r<0 || c<0 || r>=m || c>=n || g[r][c]!='1') return;
g[r][c] = '0';
dfs(g,r+1,c); dfs(g,r-1,c); dfs(g,r,c+1); dfs(g,r,c-1);
}
int numIslands(vector<vector<char>>& grid) {
int cnt=0;
for(int r=0;r<[Link]();r++) for(int c=0;c<grid[0].size();c++)
if(grid[r][c]=='1') { cnt++; dfs(grid,r,c); }
return cnt;
}
};

Complexity + Tips
Time O(m*n), stack O(m*n) worst.
This is DFS recursion, not choice recursion.

12.4 LeetCode 695 Max Area of Island

Question samjho
Grid me largest connected 1s ka area find karna hai.

Approach Hinglish
Each DFS returns area of current island. Mark visited by setting 0.

Equation / Recurrence
area(r,c)=1+areas(neighbors)

class Solution {
public:
int dfs(vector<vector<int>>& g, int r, int c) {
int m=[Link](), n=g[0].size();
if(r<0||c<0||r>=m||c>=n||g[r][c]==0) return 0;
g[r][c]=0;
return 1 + dfs(g,r+1,c) + dfs(g,r-1,c) + dfs(g,r,c+1) + dfs(g,r,c-1);
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int best=0;
for(int r=0;r<[Link]();r++) for(int c=0;c<grid[0].size();c++)
best=max(best, dfs(grid,r,c));
return best;
}
};

Complexity + Tips
Time O(m*n), stack O(m*n).

13. Classic Hard Backtracking

13.1 LeetCode 51 N-Queens
Question samjho
n queens ko n*n board pe place karna hai so no two attack each other.

Approach Hinglish
Row by row queen place karo. Column and diagonals track karo.

Equation / Recurrence
col[c], diag1[r-c+n-1], diag2[r+c]

class Solution {
public:
vector<vector<string>> ans;
void dfs(int r, int n, vector<string>& board, vector<int>& col, vector<int>& d1, vector<int>& d2) {

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 if (r == n) { ans.push_back(board); return; }
for (int c = 0; c < n; c++) {
if (col[c] || d1[r - c + n - 1] || d2[r + c]) continue;
board[r][c] = 'Q'; col[c] = d1[r-c+n-1] = d2[r+c] = 1;
dfs(r + 1, n, board, col, d1, d2);
board[r][c] = '.'; col[c] = d1[r-c+n-1] = d2[r+c] = 0;
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
vector<int> col(n), d1(2*n), d2(2*n);
dfs(0, n, board, col, d1, d2);
return ans;
}
};

Complexity + Tips
Rough O(n!), stack O(n).
Diagonal equations yad rakho: r-c constant, r+c constant.

13.2 LeetCode 37 Sudoku Solver

Question samjho
9x9 Sudoku fill karna hai. Empty cells . hain. Row, column, box constraints follow hone chahiye.

Approach Hinglish
Find empty cell. Try digits 1..9. Valid ho to place, solve rest, fail ho to undo.

Equation / Recurrence
backtrack cell by cell

class Solution {
public:
bool valid(vector<vector<char>>& b, int r, int c, char ch) {
for (int i = 0; i < 9; i++) {
if (b[r][i] == ch || b[i][c] == ch) return false;
int br = 3 * (r / 3) + i / 3;
int bc = 3 * (c / 3) + i % 3;
if (b[br][bc] == ch) return false;
}
return true;
}
bool solve(vector<vector<char>>& b) {
for (int r=0;r<9;r++) for (int c=0;c<9;c++) if (b[r][c]=='.') {
for (char ch='1'; ch<='9'; ch++) {
if (valid(b,r,c,ch)) {
b[r][c]=ch;
if (solve(b)) return true;
b[r][c]='.';
}
}
return false;
}
return true;
}
void solveSudoku(vector<vector<char>>& board) { solve(board); }
};

Complexity + Tips
Backtracking exponential but fine for 9x9.
Return bool because only one solution needed.

13.3 LeetCode 698 Partition to K Equal Sum Subsets

Question samjho
Array ko k subsets me split karna hai jinka sum equal ho.

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 Approach Hinglish
Total sum divisible by k hona chahiye. Backtrack numbers into buckets.

Equation / Recurrence
target = sum/k, fill buckets

class Solution {
public:
bool dfs(vector<int>& nums, vector<int>& bucket, int idx, int target) {
if (idx == [Link]()) return true;
int x = nums[idx];
for (int i = 0; i < [Link](); i++) {
if (bucket[i] + x > target) continue;
bucket[i] += x;
if (dfs(nums, bucket, idx + 1, target)) return true;
bucket[i] -= x;
if (bucket[i] == 0) break; // avoid symmetric empty buckets
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate([Link](), [Link](), 0);
if (sum % k) return false;
sort([Link](), [Link]());
vector<int> bucket(k, 0);
return dfs(nums, bucket, 0, sum / k);
}
};

Complexity + Tips
Exponential, pruning important.
Sort descending = big stones first, search fast cut hota hai.

14. Recursion in Linked List

14.1 Reverse Linked List Recursively
Question samjho
Linked list reverse karni hai.

Approach Hinglish
Head ke baad wali list reverse ho jaye. Fir head ko end me attach karo.

Equation / Recurrence
reverse(head)=newHead of reverse(head->next)

ListNode* reverseList(ListNode* head) {

if (!head || !head->next) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}

Complexity + Tips
Time O(n), stack O(n).
Dry run 1->2->3. Returning pe 3->2, then 2->1.

14.2 Merge Two Sorted Lists Recursive

Question samjho
Two sorted linked lists merge karni hain.

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 Approach Hinglish
Smaller head choose karo. Uska next merge of remaining lists hoga.

Equation / Recurrence
merge(a,b)=min head + merge(rest,other)

ListNode* mergeTwoLists(ListNode* a, ListNode* b) {

if (!a) return b;
if (!b) return a;
if (a->val <= b->val) {
a->next = mergeTwoLists(a->next, b);
return a;
} else {
b->next = mergeTwoLists(a, b->next);
return b;
}
}

Complexity + Tips
Time O(n+m), stack O(n+m).

14.3 Swap Nodes in Pairs

Question samjho
List ke adjacent pairs swap karne hain. 1->2->3->4 becomes 2->1->4->3.

Approach Hinglish
First two nodes swap karo. Baaki list recursively swap.

Equation / Recurrence
newHead=head->next; head->next=swap(rest)

ListNode* swapPairs(ListNode* head) {

if (!head || !head->next) return head;
ListNode* second = head->next;
head->next = swapPairs(second->next);
second->next = head;
return second;
}

Complexity + Tips
Time O(n), stack O(n).
Pointer rewiring carefully karo.

15. Recursion in Trees

Tree recursion mantra
Binary tree me function usually current node ke answer ko left subtree and right subtree ke answers se combine karta hai. Base case node == NULL.

15.1 Tree Traversals

Question samjho
Binary tree nodes ko different order me visit karna hai.

Approach Hinglish
Preorder: root-left-right. Inorder: left-root-right. Postorder: left-right-root.

Equation / Recurrence
Base: null return

void preorder(TreeNode* root) {

if (!root) return;
cout << root->val << " ";
Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision
 preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}

Complexity + Tips
Time O(n), stack O(height).
Tree recursion ka hello-world.

15.2 Max Depth of Binary Tree

Question samjho
Tree ki height/depth nikalni hai.

Approach Hinglish
Depth = 1 + max(left depth, right depth).

Equation / Recurrence
D(node)=1+max(D(left),D(right)), D(null)=0

int maxDepth(TreeNode* root) {

if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

Complexity + Tips
Time O(n), stack O(h).

15.3 Diameter of Binary Tree

Question samjho
Tree me longest path length between any two nodes find karna hai. Path root se pass ho ya na ho.

Approach Hinglish
At every node, candidate diameter = leftHeight + rightHeight. Height return karo, global best update karo.

Equation / Recurrence
height=1+max(L,R), diameter=max(diameter,L+R)

class Solution {
public:
int best = 0;
int height(TreeNode* root) {
if (!root) return 0;
int L = height(root->left);
int R = height(root->right);
best = max(best, L + R);
return 1 + max(L, R);
}
int diameterOfBinaryTree(TreeNode* root) {
height(root);
return best;
}
};

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 Complexity + Tips
Time O(n), stack O(h).
Return height, update answer. This pattern repeats a lot.

15.4 Balanced Binary Tree

Question samjho
Har node ke left and right subtree heights ka difference <=1 hai ya nahi.

Approach Hinglish
Postorder recursion. Height return karo. Agar subtree unbalanced to -1 return.

Equation / Recurrence
height or -1 sentinel

class Solution {
public:
int check(TreeNode* root) {
if (!root) return 0;
int L = check(root->left); if (L == -1) return -1;
int R = check(root->right); if (R == -1) return -1;
if (abs(L - R) > 1) return -1;
return 1 + max(L, R);
}
bool isBalanced(TreeNode* root) {
return check(root) != -1;
}
};

Complexity + Tips
Time O(n), stack O(h).
Avoid O(n^2) by computing height once.

15.5 Path Sum

Question samjho
Root-to-leaf path ka sum target ke equal hai ya nahi.

Approach Hinglish
At node, target se node value subtract karo. Leaf pe check target == val.

Equation / Recurrence
has(node,sum)=has(left,sum-val)||has(right,sum-val)

bool hasPathSum(TreeNode* root, int targetSum) {

if (!root) return false;
if (!root->left && !root->right) return targetSum == root->val;
return hasPathSum(root->left, targetSum - root->val) ||
hasPathSum(root->right, targetSum - root->val);
}

Complexity + Tips
Time O(n), stack O(h).

15.6 Path Sum II

Question samjho
All root-to-leaf paths return karne hain jinka sum target ho.

Approach Hinglish
Current path maintain karo. Leaf valid ho to answer me copy. Return pe pop.

Equation / Recurrence

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 DFS with path vector

class Solution {
public:
vector<vector<int>> ans;
void dfs(TreeNode* root, int target, vector<int>& path) {
if (!root) return;
path.push_back(root->val);
if (!root->left && !root->right && target == root->val) ans.push_back(path);
dfs(root->left, target - root->val, path);
dfs(root->right, target - root->val, path);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int> path;
dfs(root, targetSum, path);
return ans;
}
};

Complexity + Tips
Time O(n*h) for path copies, stack O(h).
Tree path problem = push, recurse, pop.

15.7 Lowest Common Ancestor

Question samjho
Two nodes p and q ka lowest common ancestor find karna hai.

Approach Hinglish
If current null/p/q return current. Left and right search. Dono side non-null to current LCA.

Equation / Recurrence
return node pointer signals found

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (!root || root == p || root == q) return root;
TreeNode* L = lowestCommonAncestor(root->left, p, q);
TreeNode* R = lowestCommonAncestor(root->right, p, q);
if (L && R) return root;
return L ? L : R;
}

Complexity + Tips
Time O(n), stack O(h).
Return value itself carries information.

15.8 Validate BST

Question samjho
Tree valid BST hai ya nahi. Left values node se smaller, right values bigger, globally.

Approach Hinglish
Min and max allowed range carry karo.

Equation / Recurrence
low < node->val < high

bool valid(TreeNode* root, long long low, long long high) {

if (!root) return true;
if (root->val <= low || root->val >= high) return false;
return valid(root->left, low, root->val) && valid(root->right, root->val, high);
}
bool isValidBST(TreeNode* root) {

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 return valid(root, LLONG_MIN, LLONG_MAX);
}

Complexity + Tips
Time O(n), stack O(h).
Local child compare is not enough. Range carry karo.

16. Divide and Conquer Recursion

16.1 Merge Sort
Question samjho
Array sort karni hai by divide and conquer.

Approach Hinglish
Array ko half me divide karo, dono halves sort karo, merge karo.

Equation / Recurrence
T(n)=2T(n/2)+O(n) -> O(n log n)

void mergeSort(vector<int>& a, int l, int r) {

if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
vector<int> temp;
int i=l, j=m+1;
while(i<=m && j<=r) temp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
while(i<=m) temp.push_back(a[i++]);
while(j<=r) temp.push_back(a[j++]);
for(int k=0;k<[Link]();k++) a[l+k]=temp[k];
}

Complexity + Tips
Time O(n log n), space O(n), stack O(log n).

16.2 Quick Sort

Question samjho
Pivot choose karke smaller left, greater right, recursively sort.

Approach Hinglish
Partition pivot ko correct place pe laata hai. Then left/right sort.

Equation / Recurrence
Average T(n)=2T(n/2)+O(n), worst O(n^2)

int partition(vector<int>& a, int l, int r) {

int pivot = a[r], i = l;
for (int j = l; j < r; j++) {
if (a[j] <= pivot) swap(a[i++], a[j]);
}
swap(a[i], a[r]);
return i;
}
void quickSort(vector<int>& a, int l, int r) {
if (l >= r) return;
int p = partition(a, l, r);
quickSort(a, l, p - 1);
quickSort(a, p + 1, r);
}

Complexity + Tips
Average O(n log n), worst O(n^2), stack average O(log n).

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

16.3 Reverse Pairs / Count Inversions Idea
Question samjho
Pairs count karne hain jahan i<j and condition true. Brute O(n^2).

Approach Hinglish
Merge sort ke during left and right sorted hote hain, so counting fast hoti hai.

Equation / Recurrence
Count left + count right + count cross

// Reverse pairs condition example: nums[i] > 2LL * nums[j]

int mergeSortCount(vector<int>& a, int l, int r) {
if (l >= r) return 0;
int m = l + (r - l) / 2;
int cnt = mergeSortCount(a, l, m) + mergeSortCount(a, m + 1, r);
int j = m + 1;
for (int i = l; i <= m; i++) {
while (j <= r && (long long)a[i] > 2LL * a[j]) j++;
cnt += j - (m + 1);
}
inplace_merge([Link]()+l, [Link]()+m+1, [Link]()+r+1);
return cnt;
}

Complexity + Tips
Time O(n log n), space depends on merge.
Sorted halves allow two pointer count.

17. Recursion + Memoization Bridge to DP

When recursion becomes DP
Agar same state baar-baar compute ho rahi hai, memoization lagao. State = function parameters that decide answer. Example fib(n), targetSum(i,sum), grid
paths(r,c).

Problem Recursive state Transition Base

Fibonacci f(n) f(n-1)+f(n-2) n<=1
Climbing Stairs f(n) f(n-1)+f(n-2) n==0/1
Unique Paths f(r,c) f(r+1,c)+f(r,c+1) out/target
Coin Change f(i,amount) take same i or skip i+1 amount==0
House Robber f(i) max(take,skip) i>=n

17.1 Climbing Stairs

Question samjho
n stairs chadhni hain. Ek baar 1 ya 2 steps le sakte ho. Kitne ways?

Approach Hinglish
Last move 1 step ya 2 step. So ways(n)=ways(n-1)+ways(n-2).

Equation / Recurrence
W(n)=W(n-1)+W(n-2)

int climbStairs(int n) {
vector<int> memo(n + 1, -1);
function<int(int)> f = [&](int k) -> int {
if (k <= 1) return 1;
if (memo[k] != -1) return memo[k];
return memo[k] = f(k - 1) + f(k - 2);
};
return f(n);
}

Complexity + Tips

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 Time O(n), stack O(n), memo O(n).
Pure recursion exponential, memo se linear.

17.2 House Robber Recursive Memo

Question samjho
Houses line me hain, adjacent rob nahi kar sakte. Max money.

Approach Hinglish
At index i: rob current and jump i+2, or skip current and go i+1.

Equation / Recurrence
f(i)=max(nums[i]+f(i+2), f(i+1))

int rob(vector<int>& nums) {

int n = [Link]();
vector<int> memo(n, -1);
function<int(int)> f = [&](int i) -> int {
if (i >= n) return 0;
if (memo[i] != -1) return memo[i];
return memo[i] = max(nums[i] + f(i + 2), f(i + 1));
};
return f(0);
}

Complexity + Tips
Time O(n), stack O(n).
Choice recursion: take vs skip.

17.3 Coin Change Recursive Memo

Question samjho
Coins unlimited hain. Amount banana hai minimum coins se.

Approach Hinglish
At amount rem, try every coin. Minimum of 1+solve(rem-coin).

Equation / Recurrence
f(rem)=min(1+f(rem-c))

int coinChange(vector<int>& coins, int amount) {

const int INF = 1e9;
vector<int> memo(amount + 1, -2);
function<int(int)> f = [&](int rem) -> int {
if (rem == 0) return 0;
if (rem < 0) return INF;
if (memo[rem] != -2) return memo[rem];
int best = INF;
for (int c : coins) best = min(best, 1 + f(rem - c));
return memo[rem] = best;
};
int ans = f(amount);
return ans >= INF ? -1 : ans;
}

Complexity + Tips
Time O(amount*coins), stack O(amount).
INF use karo, INT_MAX+1 overflow na ho.

18. Advanced Recursion Patterns and LeetCode Map

Pattern Question signals State Famous problems
Linear recursion n, array index, string index i or n Print, factorial, reverse string
Include/Exclude all subsets, subsequences, choose/not i, current 78, 90, subset sum, 494

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 choose
Combination unique combinations, order not start, target 39, 40, 77, 216
matter
Permutation all arrangements, order matters used or index 46, 47, 784
Partition split string/array into valid parts start 131, 93
Grid DFS connected cells, path search r,c,idx 79, 200, 695
Constraint Backtracking place things satisfying rules row/cell 51, 37
Tree recursion subtree answer combine node 104, 543, 110, 236
Divide conquer sort/count/half split l,r merge sort, reverse pairs
Memo recursion overlapping states state tuple 70, 198, 322

19. Recursion Mistake Checklist

 Base case missing or wrong: infinite recursion / stack overflow.
 Problem size not reducing: solve(n) calls solve(n) again.
 Backtracking undo missing: push kiya but pop nahi kiya.
 Duplicate handling wrong: sort + same-level skip samjho.
 Pass by value vs reference confusion: string/vector copies time badha deti hain.
 Global answer not cleared between test cases in platforms.
 Returning too early in for-loop: all choices explore nahi hote.
 Index out of bounds before base check.
 Tree problems me null check bhoolna.
 Memo key incomplete: state ke saare deciding parameters include karo.

20. Compact Templates

// A. Include / Exclude
void dfs(int i) {
if (i == n) { save(); return; }
dfs(i + 1); // skip
choose(i);
dfs(i + 1); // take
undo(i);
}

// B. For-loop Combination
void dfs(int start) {
save_if_needed();
for (int i = start; i < n; i++) {
if (i > start && a[i] == a[i-1]) continue; // duplicates
choose(i);
dfs(i + 1);
undo(i);
}
}

// C. Permutation with used

void dfs() {
if ([Link]() == n) { ans.push_back(cur); return; }
for (int i=0;i<n;i++) if(!used[i]) {
used[i]=1; cur.push_back(a[i]);
dfs();
cur.pop_back(); used[i]=0;
}
}

// D. Grid DFS
void dfs(int r,int c) {
if (out || blocked || visited) return;
visited = true;
for (4 directions) dfs(nr,nc);
}

// E. Tree Recursion
int solve(TreeNode* root) {
if (!root) return base;

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision

 auto L = solve(root->left);
auto R = solve(root->right);
return combine(root->val, L, R);
}

21. Problem Practice Order

Level Problems Goal
Foundation Print, factorial, sum, fibonacci, power Call stack and recurrence
Array/String Reverse, palindrome, linear search, binary search Index based recursion
Subsets 78, 90, subset sum, 494 Include/exclude mastery
Combinations 77, 39, 40, 216 Start index and duplicate skip
Permutations 46, 47, 784 Used array and swap-backtrack
String BT 17, 22, 131, 93 Build answer step by step
Grid 79, 200, 695, rat maze Visited and directions
Hard BT 51, 37, 698 Constraints and pruning
Trees 104, 543, 110, 112, 113, 236, 98 Return-value thinking
D&C/DP bridge Merge sort, reverse pairs, 70, 198, 322 Recurrence complexity and memo

22. Sir-Style Last Revision Page

Recursion sentence formula
Mera function solve(state) kya return karega? Base case kya hai? Ek step me main kya choose/work karunga? Recursive call ke baad mujhe undo karna hai kya?
Kya same state repeat ho rahi hai? Agar haan, memo lagao.

 Question me "all possible" dikhe -> backtracking.

 Question me "count ways" dikhe -> recursion + often DP.
 Question me "choose subset" dikhe -> include/exclude.
 Question me "combination" dikhe -> start index.
 Question me "permutation" dikhe -> used array or swap.
 Question me "grid connected" dikhe -> DFS visited.
 Question me "binary tree" dikhe -> left answer + right answer + root combine.
 Question me "minimum/maximum with choices" dikhe -> try choices, take min/max, memo if repeated.
 Backtracking ka heartbeat: choose -> explore -> undo.
 Recursion ka brain: base case + smaller problem + combine.

Recursion Master Notes | Hinglish DSA | Compact Sir-Style Revision