Recursion

Recursion and backtracking are powerful techniques used to solve problems by breaking them down into smaller subproblems and exploring all possible solutions. Recursion involves a function calling itself, while backtracking is a systematic way to iterate through all possible configurations of a problem.

Table of Contents

• Table of Contents
• Recursion Basics
• Backtracking Basics
• Common Patterns
  • 1. Subsets
  • 2. Combinations
  • 3. Permutations
  • 4. N-Queens
• Time and Space Complexity
• Related Leetcode Questions
  • Easy
  • Medium
  • Hard

Recursion Basics

• Definition: Recursion is a method where a function calls itself to solve a problem by breaking it down into smaller subproblems.
• Key Characteristics:
  • Base Case: The condition under which the recursion stops.
  • Recursive Case: The part where the function calls itself with a modified argument.
• Example: Factorial of a number.

  public int factorial(int n) {
      if (n == 0) return 1; // Base case
      return n * factorial(n - 1); // Recursive case
  }

• Time Complexity: O(n)
• Space Complexity: O(n) (due to the call stack)

Backtracking Basics

• Definition: Backtracking is a systematic way to iterate through all possible configurations of a problem. It builds candidates for the solution and abandons a candidate as soon as it determines that it cannot lead to a valid solution.
• Key Characteristics:
  • Pruning: Eliminating invalid candidates early in the process.
  • State Space Tree: A tree representing all possible states (solutions) of the problem.
• Example: Generating all permutations of a string.

  public List<String> permute(String s) {
      List<String> result = new ArrayList<>();
      backtrack(s.toCharArray(), 0, result);
      return result;
  }
  private void backtrack(char[] arr, int start, List<String> result) {
      if (start == arr.length - 1) {
          result.add(new String(arr));
          return;
      }
      for (int i = start; i < arr.length; i++) {
          swap(arr, start, i);
          backtrack(arr, start + 1, result);
          swap(arr, start, i); // Backtrack
      }
  }
  private void swap(char[] arr, int i, int j) {
      char temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }

• Time Complexity: O(n!) (for permutations)
• Space Complexity: O(n) (due to the call stack)

Common Patterns

1. Subsets

• Problem: Generate all possible subsets of a set.
• Example:

  public List<List<Integer>> subsets(int[] nums) {
      List<List<Integer>> result = new ArrayList<>();
      backtrack(nums, 0, new ArrayList<>(), result);
      return result;
  }
  private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
      result.add(new ArrayList<>(path));
      for (int i = start; i < nums.length; i++) {
          path.add(nums[i]);
          backtrack(nums, i + 1, path, result);
          path.remove(path.size() - 1); // Backtrack
      }
  }

• Time Complexity: O(2^n)
• Space Complexity: O(n)

2. Combinations

• Problem: Generate all possible combinations of k elements from a set.
• Example:

  public List<List<Integer>> combine(int n, int k) {
      List<List<Integer>> result = new ArrayList<>();
      backtrack(n, k, 1, new ArrayList<>(), result);
      return result;
  }
  private void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> result) {
      if (path.size() == k) {
          result.add(new ArrayList<>(path));
          return;
      }
      for (int i = start; i <= n; i++) {
          path.add(i);
          backtrack(n, k, i + 1, path, result);
          path.remove(path.size() - 1); // Backtrack
      }
  }

• Time Complexity: O(C(n, k)) (where C(n, k) is the number of combinations)
• Space Complexity: O(k)

3. Permutations

• Problem: Generate all possible permutations of a set.
• Example:

  public List<List<Integer>> permute(int[] nums) {
      List<List<Integer>> result = new ArrayList<>();
      backtrack(nums, new ArrayList<>(), result);
      return result;
  }
  private void backtrack(int[] nums, List<Integer> path, List<List<Integer>> result) {
      if (path.size() == nums.length) {
          result.add(new ArrayList<>(path));
          return;
      }
      for (int i = 0; i < nums.length; i++) {
          if (path.contains(nums[i])) continue; // Skip duplicates
          path.add(nums[i]);
          backtrack(nums, path, result);
          path.remove(path.size() - 1); // Backtrack
      }
  }

• Time Complexity: O(n!)
• Space Complexity: O(n)

4. N-Queens

• Problem: Place n queens on an n x n chessboard such that no two queens threaten each other.
• Example:

  public List<List<String>> solveNQueens(int n) {
      List<List<String>> result = new ArrayList<>();
      char[][] board = new char[n][n];
      for (char[] row : board) {
          Arrays.fill(row, '.');
      }
      backtrack(board, 0, result);
      return result;
  }
  private void backtrack(char[][] board, int row, List<List<String>> result) {
      if (row == board.length) {
          result.add(construct(board));
          return;
      }
      for (int col = 0; col < board.length; col++) {
          if (isValid(board, row, col)) {
              board[row][col] = 'Q';
              backtrack(board, row + 1, result);
              board[row][col] = '.'; // Backtrack
          }
      }
  }
  private boolean isValid(char[][] board, int row, int col) {
      for (int i = 0; i < row; i++) {
          if (board[i][col] == 'Q') return false;
      }
      for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
          if (board[i][j] == 'Q') return false;
      }
      for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
          if (board[i][j] == 'Q') return false;
      }
      return true;
  }
  private List<String> construct(char[][] board) {
      List<String> res = new ArrayList<>();
      for (char[] row : board) {
          res.add(new String(row));
      }
      return res;
  }

• Time Complexity: O(n!)
• Space Complexity: O(n^2)

Time and Space Complexity

Problem	Time Complexity	Space Complexity
Subsets	O(2^n)	O(n)
Combinations	O(C(n, k))	O(k)
Permutations	O(n!)	O(n)
N-Queens	O(n!)	O(n^2)

Related Leetcode Questions

Easy

1. Subsets
2. Combinations
3. Permutations

Medium

1. N-Queens
2. Generate Parentheses
3. Word Search

Hard

1. Sudoku Solver
2. Palindrome Partitioning
3. Word Break II