Understanding Recursion and Backtracking
Recursion
Recursion is a programming technique where a function calls itself to solve a problem. It's a powerful tool for solving complex problems by breaking them down into smaller, more manageable subproblems.
Key Components of Recursion:
- Base case: The condition that stops the recursion
- Recursive case: The part where the function calls itself
Example: Factorial Calculation
Let's implement a factorial function recursively in both Java and C++:
Java Implementation
public class Factorial {
public static int factorial(int n) {
// Base case
if (n == 0 || n == 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println(factorial(5)); // Output: 120
}
}
C++ Implementation
#include <iostream>
int factorial(int n) {
// Base case
if (n == 0 || n == 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
int main() {
std::cout << factorial(5) << std::endl; // Output: 120
return 0;
}
In both implementations, the base case is when n is 0 or 1, and the recursive case multiplies n by the factorial of n-1.
Backtracking
Backtracking is an algorithmic technique that considers searching every possible combination in order to solve a computational problem. It builds candidates to the solution incrementally and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot lead to a valid solution.
Key Steps in Backtracking:
- Choose: Select a candidate
- Constraint: Check if the candidate satisfies the problem constraints
- Goal: Check if the candidate is a valid solution
- Recurse: Recursively apply the algorithm to build the solution
- Unchoose: If the candidate doesn't lead to a solution, undo the choice
Example: N-Queens Problem
Let's implement the N-Queens problem using backtracking in both Java and C++:
Java Implementation
import java.util.ArrayList;
import java.util.List;
public class NQueens {
public static List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<>();
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
backtrack(board, 0, solutions);
return solutions;
}
private static void backtrack(char[][] board, int row, List<List<String>> solutions) {
if (row == board.length) {
solutions.add(constructSolution(board));
return;
}
for (int col = 0; col < board.length; col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q';
backtrack(board, row + 1, solutions);
board[row][col] = '.'; // Backtrack
}
}
}
private static boolean isValid(char[][] board, int row, int col) {
// 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 < board.length; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
private static List<String> constructSolution(char[][] board) {
List<String> solution = new ArrayList<>();
for (char[] row : board) {
solution.add(new String(row));
}
return solution;
}
public static void main(String[] args) {
List<List<String>> solutions = solveNQueens(4);
for (List<String> solution : solutions) {
for (String row : solution) {
System.out.println(row);
}
System.out.println();
}
}
}
C++ Implementation
#include <iostream>
#include <vector>
#include <string>
class Solution {
public:
std::vector<std::vector<std::string>> solveNQueens(int n) {
std::vector<std::vector<std::string>> solutions;
std::vector<std::string> board(n, std::string(n, '.'));
backtrack(board, 0, solutions);
return solutions;
}
private:
void backtrack(std::vector<std::string>& board, int row, std::vector<std::vector<std::string>>& solutions) {
if (row == board.size()) {
solutions.push_back(board);
return;
}
for (int col = 0; col < board.size(); col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q';
backtrack(board, row + 1, solutions);
board[row][col] = '.'; // Backtrack
}
}
}
bool isValid(const std::vector<std::string>& board, int row, int col) {
// 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 < board.size(); i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
};
int main() {
Solution sol;
std::vector<std::vector<std::string>> solutions = sol.solveNQueens(4);
for (const auto& solution : solutions) {
for (const auto& row : solution) {
std::cout << row << std::endl;
}
std::cout << std::endl;
}
return 0;
}
In both implementations, we use backtracking to solve the N-Queens problem. The backtrack function tries placing a queen in each column of the current row. If it's a valid placement, it moves to the next row. If no valid solution is found, it backtracks by removing the queen and tries the next column.
These examples demonstrate how recursion and backtracking can be used to solve complex problems efficiently.
More Backtracking Problems for Interviews
Backtracking is a popular topic in coding interviews. Here are three more classic backtracking problems often asked in interviews, along with their implementations in both Java and C++:
1. Sudoku Solver
The Sudoku Solver problem asks you to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 sub-boxes contains all of the digits from 1 to 9.
Java Implementation
class SudokuSolver {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board))
return true;
else
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == c) return false;
if (board[row][i] == c) return false;
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
}
return true;
}
}
C++ Implementation
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
private:
bool solve(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board))
return true;
else
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
bool isValid(vector<vector<char>>& board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == c) return false;
if (board[row][i] == c) return false;
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
}
return true;
}
};
2. Permutations
The Permutations problem asks you to generate all possible permutations of a given array of distinct integers.
Java Implementation
class Permutations {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
if (tempList.contains(nums[i])) continue;
tempList.add(nums[i]);
backtrack(result, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
}
C++ Implementation
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
backtrack(result, vector<int>(), nums);
return result;
}
private:
void backtrack(vector<vector<int>>& result, vector<int>& tempList, vector<int>& nums) {
if (tempList.size() == nums.size()) {
result.push_back(tempList);
} else {
for (int i = 0; i < nums.size(); i++) {
if (find(tempList.begin(), tempList.end(), nums[i]) != tempList.end()) continue;
tempList.push_back(nums[i]);
backtrack(result, tempList, nums);
tempList.pop_back();
}
}
}
};
3. Combination Sum
The Combination Sum problem asks you to find all unique combinations of candidates where the chosen numbers sum to a target. You may return the combinations in any order.
Java Implementation
class CombinationSum {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), candidates, target, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
if (remain < 0) return;
else if (remain == 0) result.add(new ArrayList<>(tempList));
else {
for (int i = start; i < candidates.length; i++) {
tempList.add(candidates[i]);
backtrack(result, tempList, candidates, remain - candidates[i], i);
tempList.remove(tempList.size() - 1);
}
}
}
}
C++ Implementation
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> tempList;
backtrack(result, tempList, candidates, target, 0);
return result;
}
private:
void backtrack(vector<vector<int>>& result, vector<int>& tempList, vector<int>& candidates, int remain, int start) {
if (remain < 0) return;
else if (remain == 0) result.push_back(tempList);
else {
for (int i = start; i < candidates.size(); i++) {
tempList.push_back(candidates[i]);
backtrack(result, tempList, candidates, remain - candidates[i], i);
tempList.pop_back();
}
}
}
};
These problems demonstrate different aspects of backtracking:
- Sudoku Solver: Shows how to use backtracking to solve a constraint satisfaction problem.
- Permutations: Illustrates generating all possible arrangements of a set of numbers.
- Combination Sum: Demonstrates finding all possible combinations that satisfy a specific condition.
In each of these problems, the backtracking algorithm explores all possible solutions, abandoning those that don't meet the criteria and continuing with those that do. This systematic exploration of the solution space is what makes backtracking so powerful for solving complex problems.