Master the art of solving problems by exploring all possibilities. From recursive fundamentals and design patterns to advanced backtracking algorithms like N-Queens and Sudoku solvers, learn how to elegantly handle complex search problems with pruning optimization.
Recursion is a problem-solving technique where a function calls itself to solve smaller instances of the same problem.
Every recursive function requires two essential components:
public static int Factorial(int n) { // Base case: 0! = 1 if (n == 0) return 1; // Recursive case: n! = n * (n-1)! return n * Factorial(n - 1); }
For Factorial(5): 5 * Factorial(4) = 5 * (4 * (3 * (2 * (1 * 1)))) = 120
// Naive recursive - Exponential time O(2^n), redoes work public static int FibNaive(int n) { if (n <= 1) return n; return FibNaive(n - 1) + FibNaive(n - 2); } // Memoized - O(n) time, O(n) space public static int FibMemo(int n, Dictionary<int, int> memo = null) { memo ??= new Dictionary<int, int>(); if (n <= 1) return n; if (memo.ContainsKey(n)) return memo[n]; int result = FibMemo(n - 1, memo) + FibMemo(n - 2, memo); memo[n] = result; return result; }
// Calculate x^n in O(log n) time using exponentiation by squaring public static double Power(double x, int n) { if (n == 0) return 1.0; double half = Power(x, n / 2); if (n % 2 == 0) return half * half; else return half * half * x; }
Time Complexity: O(log n) - Each call reduces exponent by half. Space: O(log n) for recursion depth.
Understanding how function calls are managed is critical for writing correct and efficient recursive code.
When a function is called, a new stack frame is created containing:
The stack has maximum depth (typically 1000-10000 frames). Each recursive call uses memory.
// WRONG: No base case - infinite recursion public static void BadRecursion(int n) { Console.WriteLine(n); BadRecursion(n + 1); // Always recurses! } // CORRECT: Proper base case public static void GoodRecursion(int n) { if (n > 100) return; // Base case Console.WriteLine(n); GoodRecursion(n + 1); }
Different problem structures call for different recursive approaches. Master these patterns.
Function makes exactly one recursive call. Examples: factorial, array sum, searching.
// Linear recursion: one recursive call per invocation public static int SumArray(int[] arr, int index) { if (index == arr.Length) return 0; // Base case return arr[index] + SumArray(arr, index + 1); // Single call } public static int BinarySearch(int[] arr, int target, int left, int right) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) return BinarySearch(arr, target, mid + 1, right); else return BinarySearch(arr, target, left, mid - 1); }
Function makes two recursive calls. Examples: tree traversal, merge sort, quicksort.
// Binary tree traversal - two recursive calls public static void Traverse(TreeNode root) { if (root == null) return; Console.WriteLine(root.Val); Traverse(root.Left); // First call Traverse(root.Right); // Second call }
Recursive call is the last operation. Compilers can optimize to iteration.
// Tail recursive: last operation is recursive call public static int FactorialTail(int n, int acc = 1) { if (n == 0) return acc; return FactorialTail(n - 1, acc * n); // Last operation is call } // Non-tail: work happens after recursive call public static int FactorialNonTail(int n) { if (n == 0) return 1; int result = FactorialNonTail(n - 1); return n * result; // Work happens AFTER call }
Every recursive algorithm can be converted to iteration using an explicit stack. Understanding both perspectives is invaluable.
// RECURSIVE: Elegant and intuitive public static void InorderRecursive(TreeNode root, List<int> result) { if (root == null) return; InorderRecursive(root.Left, result); result.Add(root.Val); InorderRecursive(root.Right, result); } // ITERATIVE: Uses explicit stack, avoids function call overhead public static List<int> InorderIterative(TreeNode root) { var result = new List<int>(); var stack = new Stack<TreeNode>(); var current = root; while (current != null || stack.Count > 0) { while (current != null) { stack.Push(current); current = current.Left; } current = stack.Pop(); result.Add(current.Val); current = current.Right; } return result; }
Backtracking systematically explores all possible solutions by building candidates incrementally and abandoning branches that cannot lead to valid solutions.
private static void Backtrack(List<T> current, List<List<T>> results) { // 1. BASE CASE: Solution is complete if (IsComplete(current)) { results.Add(new List<T>(current)); return; } // 2. EXPLORE: Try all possible next candidates foreach (var candidate in GetCandidates(current)) { // 3. CHOOSE: Add candidate current.Add(candidate); // 4. PRUNE: Check if still valid if (IsValid(current)) { // 5. RECURSE: Explore deeper Backtrack(current, results); } // 6. UNCHOOSE: Remove candidate (backtrack) current.RemoveAt(current.Count - 1); } }
Backtracking problems typically have:
Generate all possible subsets of a given set. The power set of n elements has 2^n members.
Given: [1, 2, 3] → Return: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
public static List<List<int>> Subsets(int[] nums) { var result = new List<List<int>>(); BacktrackSubsets(nums, 0, new List<int>(), result); return result; } private static void BacktrackSubsets(int[] nums, int start, List<int> current, List<List<int>> result) { // Add current subset (including empty set) result.Add(new List<int>(current)); // Try adding each remaining element for (int i = start; i < nums.Length; i++) { current.Add(nums[i]); // Choose BacktrackSubsets(nums, i + 1, current, result); // Explore current.RemoveAt(current.Count - 1); // Unchoose } }
Given: [1, 2, 2] → Return unique subsets only (skip duplicate combinations)
public static List<List<int>> SubsetsWithDup(int[] nums) { var result = new List<List<int>>(); Array.Sort(nums); // Sort to group duplicates together BacktrackSubsetsDup(nums, 0, new List<int>(), result); return result; } private static void BacktrackSubsetsDup(int[] nums, int start, List<int> current, List<List<int>> result) { result.Add(new List<int>(current)); for (int i = start; i < nums.Length; i++) { // PRUNE: Skip duplicate at same recursion level if (i > start && nums[i] == nums[i - 1]) continue; current.Add(nums[i]); BacktrackSubsetsDup(nums, i + 1, current, result); current.RemoveAt(current.Count - 1); } }
Generate all combinations of k elements from n elements. Order doesn't matter: [1,2] = [2,1].
Given: n=4, k=2 → Return: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
public static List<List<int>> Combine(int n, int k) { var result = new List<List<int>>(); BacktrackCombine(n, k, 1, new List<int>(), result); return result; } private static void BacktrackCombine(int n, int k, int start, List<int> current, List<List<int>> result) { // Base case: combination is complete if (current.Count == k) { result.Add(new List<int>(current)); return; } // Prune: not enough remaining numbers int remaining = k - current.Count; if (n - start + 1 < remaining) return; for (int i = start; i <= n; i++) { current.Add(i); BacktrackCombine(n, k, i + 1, current, result); current.RemoveAt(current.Count - 1); } }
Given: candidates=[2,3,6,7], target=7 → Return: [[2,2,3], [7]]
public static List<List<int>> CombinationSum(int[] candidates, int target) { var result = new List<List<int>>(); Array.Sort(candidates); BacktrackCombSum(candidates, target, 0, new List<int>(), result); return result; } private static void BacktrackCombSum(int[] candidates, int target, int start, List<int> current, List<List<int>> result) { if (target == 0) { result.Add(new List<int>(current)); return; } // Prune: target is negative if (target < 0) return; for (int i = start; i < candidates.Length; i++) { // Prune: candidate exceeds target if (candidates[i] > target) break; current.Add(candidates[i]); // Note: start stays same - can reuse candidates BacktrackCombSum(candidates, target - candidates[i], i, current, result); current.RemoveAt(current.Count - 1); } }
Key Difference: Pass i (not i+1) to allow reusing the same candidate.
Generate all arrangements of elements. Order matters: [1,2] ≠ [2,1]. Total: n! permutations.
Given: [1,2,3] → Return: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
public static List<List<int>> Permute(int[] nums) { var result = new List<List<int>>(); var used = new bool[nums.Length]; BacktrackPermute(nums, used, new List<int>(), result); return result; } private static void BacktrackPermute(int[] nums, bool[] used, List<int> current, List<List<int>> result) { if (current.Count == nums.Length) { result.Add(new List<int>(current)); return; } for (int i = 0; i < nums.Length; i++) { if (used[i]) continue; // Skip already used elements used[i] = true; current.Add(nums[i]); BacktrackPermute(nums, used, current, result); current.RemoveAt(current.Count - 1); used[i] = false; } }
Given: [1,1,2] → Return unique permutations only
public static List<List<int>> PermuteUnique(int[] nums) { var result = new List<List<int>>(); Array.Sort(nums); var used = new bool[nums.Length]; BacktrackPermuteUnique(nums, used, new List<int>(), result); return result; } private static void BacktrackPermuteUnique(int[] nums, bool[] used, List<int> current, List<List<int>> result) { if (current.Count == nums.Length) { result.Add(new List<int>(current)); return; } for (int i = 0; i < nums.Length; i++) { if (used[i]) continue; // PRUNE: Skip duplicate at same level if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; current.Add(nums[i]); BacktrackPermuteUnique(nums, used, current, result); current.RemoveAt(current.Count - 1); used[i] = false; } }
Place n queens on an n×n board so no two queens attack each other. A classic backtracking problem demonstrating constraint pruning.
public static List<List<string>> SolveNQueens(int n) { var result = new List<List<string>>(); var board = new char[n][]; for (int i = 0; i < n; i++) board[i] = new char[n]; InitBoard(board, n); BacktrackNQueens(board, 0, n, result); return result; } private static void InitBoard(char[][] board, int n) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) board[i][j] = '.'; } private static void BacktrackNQueens(char[][] board, int row, int n, List<List<string>> result) { // Base case: all queens placed if (row == n) { result.Add(ConvertBoard(board)); return; } // Try placing queen in each column of current row for (int col = 0; col < n; col++) { // Prune: check if placement is safe if (IsSafe(board, row, col, n)) { board[row][col] = 'Q'; BacktrackNQueens(board, row + 1, n, result); board[row][col] = '.'; } } } private static bool IsSafe(char[][] board, int row, int col, int n) { // Check column for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false; // Check upper left diagonal for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) if (board[i][j] == 'Q') return false; // Check upper right diagonal for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) if (board[i][j] == 'Q') return false; return true; } private static List<string> ConvertBoard(char[][] board) { var result = new List<string>(); foreach (var row in board) result.Add(new string(row)); return result; }
Solve a Sudoku puzzle using backtracking. A complex constraint satisfaction problem.
public static void SolveSudoku(char[][] board) { BacktrackSudoku(board); } private static bool BacktrackSudoku(char[][] board) { // Find next empty cell for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] != '.') continue; // Try digits 1-9 for (char digit = '1'; digit <= '9'; digit++) { // Prune: check if digit is valid if (IsValidSudoku(board, i, j, digit)) { board[i][j] = digit; if (BacktrackSudoku(board)) return true; board[i][j] = '.'; // Unchoose } } return false; // No valid digit found } } return true; // All cells filled } private static bool IsValidSudoku(char[][] board, int row, int col, char digit) { // Check row for (int j = 0; j < 9; j++) if (board[row][j] == digit) return false; // Check column for (int i = 0; i < 9; i++) if (board[i][col] == digit) return false; // Check 3x3 box int boxRow = (row / 3) * 3; int boxCol = (col / 3) * 3; for (int i = boxRow; i < boxRow + 3; i++) for (int j = boxCol; j < boxCol + 3; j++) if (board[i][j] == digit) return false; return true; }
m = number of given clues. Pruning constraints make it practical despite theoretical worst-case.
Search for a word in a 2D board. Each cell can only be used once per path.
Given 2D board and word, determine if word exists in board (can move up/down/left/right).
public static bool Exist(char[][] board, string word) { for (int i = 0; i < board.Length; i++) { for (int j = 0; j < board[i].Length; j++) { if (board[i][j] == word[0]) { if (BacktrackWordSearch(board, word, 0, i, j)) return true; } } } return false; } private static bool BacktrackWordSearch(char[][] board, string word, int index, int row, int col) { // Base case: entire word found if (index == word.Length) return true; // Prune: out of bounds or cell mismatch if (row < 0 || row >= board.Length || col < 0 || col >= board[0].Length || board[row][col] != word[index]) return false; // Prune: already visited if (board[row][col] == '#') return false; // Choose: mark visited char temp = board[row][col]; board[row][col] = '#'; // Explore: try all 4 directions bool found = BacktrackWordSearch(board, word, index + 1, row + 1, col) || BacktrackWordSearch(board, word, index + 1, row - 1, col) || BacktrackWordSearch(board, word, index + 1, row, col + 1) || BacktrackWordSearch(board, word, index + 1, row, col - 1); // Unchoose: unmark visited board[row][col] = temp; return found; }
N = board cells, L = word length. Each cell can branch to 4 neighbors.
Generate all possible letter combinations from a phone number (like old T9 texting).
public static List<string> LetterCombinations(string digits) { var result = new List<string>(); if (string.IsNullOrEmpty(digits)) return result; var phoneMap = new Dictionary<string, string> { { "2", "abc" }, { "3", "def" }, { "4", "ghi" }, { "5", "jkl" }, { "6", "mno" }, { "7", "pqrs" }, { "8", "tuv" }, { "9", "wxyz" } }; BacktrackPhone(digits, 0, phoneMap, new StringBuilder(), result); return result; } private static void BacktrackPhone(string digits, int index, Dictionary<string, string> phoneMap, StringBuilder current, List<string> result) { // Base case: all digits processed if (index == digits.Length) { result.Add(current.ToString()); return; } string digit = digits[index].ToString(); string letters = phoneMap[digit]; // Try each letter for current digit foreach (char letter in letters) { current.Append(letter); BacktrackPhone(digits, index + 1, phoneMap, current, result); current.Length--; } }
Example: Input: "23" → Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Generate all valid combinations of n pairs of parentheses.
public static List<string> GenerateParenthesis(int n) { var result = new List<string>(); BacktrackParens(n, 0, 0, new StringBuilder(), result); return result; } private static void BacktrackParens(int n, int openCount, int closeCount, StringBuilder current, List<string> result) { // Base case: 2n chars added if (current.Length == 2 * n) { result.Add(current.ToString()); return; } // Prune & Choose: can add opening paren? if (openCount < n) { current.Append('('); BacktrackParens(n, openCount + 1, closeCount, current, result); current.Length--; } // Prune & Choose: can add closing paren? if (closeCount < openCount) { current.Append(')'); BacktrackParens(n, openCount, closeCount + 1, current, result); current.Length--; } }
Key Insight: Can only add ')' if we have more '(' than ')'. This pruning avoids invalid sequences entirely.
Partition a string into all possible ways where each substring is a palindrome.
public static List<List<string>> Partition(string s) { var result = new List<List<string>>(); BacktrackPartition(s, 0, new List<string>(), result); return result; } private static void BacktrackPartition(string s, int start, List<string> current, List<List<string>> result) { // Base case: reached end of string if (start == s.Length) { result.Add(new List<string>(current)); return; } // Try all substrings starting from 'start' for (int end = start; end < s.Length; end++) { // Prune: only continue if substring is palindrome if (IsPalindrome(s, start, end)) { current.Add(s.Substring(start, end - start + 1)); BacktrackPartition(s, end + 1, current, result); current.RemoveAt(current.Count - 1); } } } private static bool IsPalindrome(string s, int left, int right) { while (left < right) { if (s[left] != s[right]) return false; left++; right--; } return true; }
Example: Input: "nitin" → Output: [["nitin"], ["n", "i", "t", "i", "n"], ["n", "iti", "n"]]
Effective pruning can reduce search space exponentially. Master these techniques to optimize backtracking.
Check validity before recursing deeper. Example: N-Queens checking if placement is safe.
// GOOD: Check constraints before recursing if (IsValid(currentSolution)) { Backtrack(currentSolution); } // BAD: Recurse first, then validate Backtrack(currentSolution); if (!IsValid(currentSolution)) return;
Skip equivalent candidates that lead to identical subtrees.
// Sort input first to group duplicates Array.Sort(nums); for (int i = start; i < nums.Length; i++) { // Skip if same as previous at this recursion level if (i > start && nums[i] == nums[i - 1]) continue; Backtrack(nums, i + 1); }
Use math to eliminate branches that cannot yield solutions.
// Example: Combination generation - not enough remaining elements int remaining = k - current.Count; if (n - start + 1 < remaining) return; // Not enough elements left, prune // Example: Target sum - exceeds limit if (currentSum > target) return; // Can't reach target, prune
Cache subproblem results to avoid recomputing.
// Store computed results private HashSet<string> memo = new HashSet<string>(); private void Backtrack(...) { string key = GetKey(currentState); if (memo.Contains(key)) return; // Solve and memoize memo.Add(key); }
| Without Pruning | With Pruning | Problem |
|---|---|---|
| n^n | N! or 2^N | N-Queens |
| 9^81 | Practical | Sudoku |
| 2^N × N | N × 2^N | Subsets with duplicates |
| Unlimited | Finishes | Word Search |
Practical guidance for solving recursion and backtracking problems in technical interviews.
Time Complexity:
Space Complexity:
Example Script:
"This is a subset generation problem. I need all 2^N combinations of the array. I'll use backtracking: iterate through elements, choose each one, recurse, then unchoose to try alternatives. Since there are duplicates, I'll sort first, then skip consecutive equal elements at each recursion level to avoid duplicate subsets. Time is O(N × 2^N) because I have 2^N subsets and each takes O(N) to copy. Space is O(2^N) for storing results."