DSA Sheet - Day 9 Recursion and Backtracking

🚀 DSA Sheet – Day 9: Recursion & Backtracking

This section focuses on recursion trees and backtracking patterns. These problems test your ability to explore all possibilities efficiently with pruning.

📊 Progress Tracker

Progress: 0 / 6 Completed

Done	Problem	Practice	Level	Companies
	Combination Sum I	Solve	Medium	Salesforce, Oracle
	Combination Sum II	Solve	Medium	Amazon, Microsoft
	Palindrome Partitioning	Solve	Medium	Meta, Microsoft
	N Queens	Solve	Hard	Google, Oracle
	Sudoku Solver	Solve	Hard	Amazon, Microsoft
	M-Coloring Problem	Solve	Hard	Google

🧠 Key Approaches

• Combination Sum: Pick / Not Pick recursion pattern
• Combination Sum II: Skip duplicates carefully
• Palindrome Partitioning: Backtracking + palindrome check
• N Queens: Place queens safely (columns + diagonals)
• Sudoku Solver: Try digits 1–9 with validation
• M-Coloring: Assign colors with constraint checking

⚡ Quick Cheatsheet

Combination Sum (Recursion Pattern)

void solve(int i, int target){
  if(target == 0){
    // store answer
    return;
  }

  if(i == n) return;

  // pick
  if(arr[i] <= target)
    solve(i, target - arr[i]);

  // not pick
  solve(i + 1, target);
}
    

Palindrome Check

bool isPal(string s){
  int l = 0, r = s.size() - 1;

  while(l < r){
    if(s[l++] != s[r--]) 
      return false;
  }
  return true;
}
    

N-Queens Safety Check

bool isSafe(int row, int col){
  // check column
  // check upper diagonal
  // check lower diagonal
}
    

🔥 Pro Tip

Backtracking is about exploring choices:

• Make a choice
• Explore recursively
• Undo (backtrack)

Think in terms of recursion trees — that’s the key to mastering this topic.

🏠 All Days ⬅ Previous Next ➡