Loading W Code...
Recursion basics, Backtracking, N-Queens, Sudoku Solver & more.
Imagine a set of Russian nesting dolls. Each doll looks identical to the outer doll but is smaller in size. You open them one by one until you reach the smallest, solid doll that cannot be opened (the base case). Once reached, you stop opening and start assembling them back.
Recursion is a programming technique where a function calls itself directly or indirectly to solve a smaller instance of the same problem.
Each recursive call pauses the current execution state and pushes a new stack frame onto the system Call Stack. Once the base case triggers, stack frames are popped off sequentially, returning control back upward.
#include <iostream>
using namespace std;
// Simple recursion: Countdown
void countdown(int n) {
// Base case
if (n <= 0) {
cout << "Blast off!" << endl;
return;
}
// Recursive case
cout << n << endl;
countdown(n - 1); // Smaller problem
}
// Factorial: n! = n * (n-1)!
int factorial(int n) {
// Base case
if (n <= 1) return 1;
// Recursive case
return n * factorial(n - 1);
}
// Sum of digits
int sumOfDigits(int n) {
if (n == 0) return 0;
return (n % 10) + sumOfDigits(n / 10);
}
// Print numbers 1 to n (tail recursion)
void printNumbers(int n, int current = 1) {
if (current > n) return;
cout << current << " ";
printNumbers(n, current + 1);
}
int main() {
countdown(3);
cout << endl;
cout << "5! = " << factorial(5) << endl; // 120
cout << "Sum of digits of 1234: " << sumOfDigits(1234) << endl; // 10
cout << "1 to 5: ";
printNumbers(5);
cout << endl;
return 0;
}Imagine measuring a long line of students. Instead of walking the line yourself, you ask the first student their height, then tell them to request the height of the remaining line from the student behind them. They repeat this until the last student responds, and the heights are summed back to you.
When working with arrays or strings recursively, we avoid making copies of the data structure (which wastes memory). Instead, we pass index pointers as function parameters to track our active search window.
0 up to n - 1 or shrinking indices from both ends towards the center (e.g., palindrome validation).#include <iostream>
#include <string>
#include <vector>
using namespace std;
// Sum of array
int arraySum(vector<int>& arr, int index = 0) {
if (index == arr.size()) return 0;
return arr[index] + arraySum(arr, index + 1);
}
// Check if array is sorted
bool isSorted(vector<int>& arr, int index = 0) {
if (index >= arr.size() - 1) return true;
if (arr[index] > arr[index + 1]) return false;
return isSorted(arr, index + 1);
}
// Linear search using recursion
int linearSearch(vector<int>& arr, int target, int index = 0) {
if (index == arr.size()) return -1;
if (arr[index] == target) return index;
return linearSearch(arr, target, index + 1);
}
// Reverse a string
string reverseString(string s) {
if (s.length() <= 1) return s;
return reverseString(s.substr(1)) + s[0];
}
// Check palindrome
bool isPalindrome(string s, int left, int right) {
if (left >= right) return true;
if (s[left] != s[right]) return false;
return isPalindrome(s, left + 1, right - 1);
}
bool isPalindrome(string s) {
return isPalindrome(s, 0, s.length() - 1);
}
// Find first occurrence
int firstOccurrence(string s, char c, int index = 0) {
if (index == s.length()) return -1;
if (s[index] == c) return index;
return firstOccurrence(s, c, index + 1);
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
cout << "Sum: " << arraySum(arr) << endl; // 15
cout << "Sorted: " << (isSorted(arr) ? "Yes" : "No") << endl; // Yes
cout << "Index of 3: " << linearSearch(arr, 3) << endl; // 2
cout << "Reverse 'hello': " << reverseString("hello") << endl; // olleh
cout << "Is 'radar' palindrome: " << (isPalindrome("radar") ? "Yes" : "No") << endl; // Yes
return 0;
}Imagine exploring a maze. When you reach a dead end, you don't teleport back to the start. Instead, you turn around, walk backward to the last intersection you passed, and try a different direction.
Backtracking is a refined depth-first search (DFS) optimization. It systematically explores a decision tree, and if it determines that a path cannot lead to a valid solution, it discards it by "undoing" the last step (backtracking) and tries the next branch.
void backtrack(State state) {
if (is_solution(state)) {
save_result(state);
return;
}
for (Choice choice : get_choices(state)) {
if (is_valid(choice)) {
apply_choice(choice);
backtrack(next_state);
undo_choice(choice); // The actual backtrack step
}
}
}
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Generate all subsets (Power Set)
void generateSubsets(vector<int>& nums, int index, vector<int>& current,
vector<vector<int>>& result) {
// Base case: processed all elements
if (index == nums.size()) {
result.push_back(current);
return;
}
// Choice 1: Don't include current element
generateSubsets(nums, index + 1, current, result);
// Choice 2: Include current element
current.push_back(nums[index]);
generateSubsets(nums, index + 1, current, result);
current.pop_back(); // BACKTRACK!
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
generateSubsets(nums, 0, current, result);
return result;
}
// Generate all permutations
void generatePermutations(vector<int>& nums, vector<int>& current,
vector<bool>& used, vector<vector<int>>& result) {
if (current.size() == nums.size()) {
result.push_back(current);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue;
// Make choice
used[i] = true;
current.push_back(nums[i]);
generatePermutations(nums, current, used, result);
// Backtrack
current.pop_back();
used[i] = false;
}
}
vector<vector<int>> permutations(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
vector<bool> used(nums.size(), false);
generatePermutations(nums, current, used, result);
return result;
}
int main() {
// Subsets
vector<int> nums1 = {1, 2, 3};
auto allSubsets = subsets(nums1);
cout << "Subsets of [1,2,3]:" << endl;
for (auto& subset : allSubsets) {
cout << "[ ";
for (int x : subset) cout << x << " ";
cout << "]" << endl;
}
cout << endl;
// Permutations
vector<int> nums2 = {1, 2, 3};
auto allPerms = permutations(nums2);
cout << "Permutations of [1,2,3]:" << endl;
for (auto& perm : allPerms) {
cout << "[ ";
for (int x : perm) cout << x << " ";
cout << "]" << endl;
}
return 0;
}The N-Queens problem asks us to place N chess queens on an N × N chessboard such that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal path.
Since each row can contain exactly one queen, we can place queens row by row:
For any grid position (r, c):
row - col.row + col.
We use lookup tables (boolean arrays) to verify diagonal safety in O(1) time.#include <iostream>
#include <vector>
#include <string>
using namespace std;
class NQueens {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> solutions;
vector<string> board(n, string(n, '.'));
vector<bool> cols(n, false); // Column occupied
vector<bool> diag1(2 * n, false); // row - col + n
vector<bool> diag2(2 * n, false); // row + col
backtrack(0, n, board, cols, diag1, diag2, solutions);
return solutions;
}
private:
void backtrack(int row, int n, vector<string>& board,
vector<bool>& cols, vector<bool>& diag1, vector<bool>& diag2,
vector<vector<string>>& solutions) {
// Base case: all queens placed
if (row == n) {
solutions.push_back(board);
return;
}
// Try placing queen in each column
for (int col = 0; col < n; col++) {
int d1 = row - col + n; // Diagonal index 1
int d2 = row + col; // Diagonal index 2
// Check if position is safe
if (cols[col] || diag1[d1] || diag2[d2]) {
continue; // Not safe
}
// Place queen
board[row][col] = 'Q';
cols[col] = diag1[d1] = diag2[d2] = true;
// Move to next row
backtrack(row + 1, n, board, cols, diag1, diag2, solutions);
// Remove queen (backtrack)
board[row][col] = '.';
cols[col] = diag1[d1] = diag2[d2] = false;
}
}
};
void printBoard(vector<string>& board) {
for (string& row : board) {
cout << row << endl;
}
cout << endl;
}
int main() {
NQueens solver;
// Solve for 4 queens
auto solutions = solver.solveNQueens(4);
cout << "4-Queens Solutions: " << solutions.size() << endl << endl;
for (auto& solution : solutions) {
printBoard(solution);
}
return 0;
}A Sudoku solver fills an incomplete 9 × 9 grid such that every row, every column, and each of the nine 3 × 3 subgrids contain all digits from 1 to 9 without repeating.
'.').1 through 9 in that cell.false), clear the cell (set it back to '.') and try the next candidate digit.#include <iostream>
#include <vector>
using namespace std;
class SudokuSolver {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}
private:
bool solve(vector<vector<char>>& board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == '.') {
// Try digits 1-9
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, row, col, c)) {
board[row][col] = c; // Place digit
if (solve(board)) {
return true; // Solved!
}
board[row][col] = '.'; // Backtrack
}
}
return false; // No valid digit found
}
}
}
return true; // All cells filled
}
bool isValid(vector<vector<char>>& board, int row, int col, char c) {
// Check row
for (int i = 0; i < 9; i++) {
if (board[row][i] == c) return false;
}
// Check column
for (int i = 0; i < 9; i++) {
if (board[i][col] == c) return false;
}
// Check 3x3 box
int boxRow = (row / 3) * 3;
int boxCol = (col / 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[boxRow + i][boxCol + j] == c) return false;
}
}
return true;
}
};
void printBoard(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
if (i % 3 == 0 && i != 0) {
cout << "------+-------+------" << endl;
}
for (int j = 0; j < 9; j++) {
if (j % 3 == 0 && j != 0) cout << "| ";
cout << board[i][j] << " ";
}
cout << endl;
}
}
int main() {
vector<vector<char>> board = {
{'5','3','.','.','7','.','.','.','.'},
{'6','.','.','1','9','5','.','.','.'},
{'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'},
{'4','.','.','8','.','3','.','.','1'},
{'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'},
{'.','.','.','4','1','9','.','.','5'},
{'.','.','.','.','8','.','.','7','9'}
};
SudokuSolver solver;
solver.solveSudoku(board);
printBoard(board);
return 0;
}A common category of backtracking problems involves finding subsets of numbers that sum up to a target value.
To prevent generating duplicate combinations or checking redundant paths, we sort the candidates list initially:
candidates[i] == candidates[i - 1] and skip it if we're generating unique-use sets.#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Combination Sum I: Elements can be used multiple times
void combinationSum1(vector<int>& candidates, int target, int start,
vector<int>& current, vector<vector<int>>& result) {
if (target == 0) {
result.push_back(current);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (candidates[i] > target) break; // Pruning (array is sorted)
current.push_back(candidates[i]);
combinationSum1(candidates, target - candidates[i], i, current, result); // Can reuse
current.pop_back();
}
}
// Combination Sum II: Each element used at most once
void combinationSum2(vector<int>& candidates, int target, int start,
vector<int>& current, vector<vector<int>>& result) {
if (target == 0) {
result.push_back(current);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (candidates[i] > target) break;
// Skip duplicates
if (i > start && candidates[i] == candidates[i - 1]) continue;
current.push_back(candidates[i]);
combinationSum2(candidates, target - candidates[i], i + 1, current, result); // Can't reuse
current.pop_back();
}
}
// Partition into K equal sum subsets
bool backtrack(vector<int>& nums, vector<bool>& used, int start,
int k, int currentSum, int target) {
if (k == 0) return true; // All subsets filled
if (currentSum == target) {
return backtrack(nums, used, 0, k - 1, 0, target); // Start next subset
}
for (int i = start; i < nums.size(); i++) {
if (used[i] || currentSum + nums[i] > target) continue;
used[i] = true;
if (backtrack(nums, used, i + 1, k, currentSum + nums[i], target)) {
return true;
}
used[i] = false;
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = 0;
for (int n : nums) sum += n;
if (sum % k != 0) return false;
int target = sum / k;
sort(nums.rbegin(), nums.rend()); // Sort descending for pruning
vector<bool> used(nums.size(), false);
return backtrack(nums, used, 0, k, 0, target);
}
int main() {
// Combination Sum I
vector<int> candidates1 = {2, 3, 6, 7};
sort(candidates1.begin(), candidates1.end());
vector<vector<int>> result1;
vector<int> current1;
combinationSum1(candidates1, 7, 0, current1, result1);
cout << "Combinations summing to 7 (can reuse):" << endl;
for (auto& comb : result1) {
cout << "[ ";
for (int x : comb) cout << x << " ";
cout << "]" << endl;
}
return 0;
}