Recursive Implementation of Combinatorial Enumeration

Given two integers n and m, generate all combinations of m distinct integers from the set {1, 2, ..., n} in lexicographical order.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> results;
vector<int> current;
int total, count;

void explore(int start) {
    if (current.size() == count) {
        results.push_back(current);
        return;
    }
    
    for (int i = start; i <= total; i++) {
        current.push_back(i);
        explore(i + 1);
        current.pop_back();
    }
}

int main() {
    cin >> total >> count;
    for (int i = 1; i <= total; i++) {
        explore(i);
    }
    
    for (auto& combination : results) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }
}

N-Queens Problem

Place n queens on an n×n chessboard such that no two queens threaten each other. Count the number of distinct solutions.

Approach 1: State Management in Parent Node

#include <iostream>
#include <vector>
using namespace std;

int solutions = 0;
int board_size;
vector<bool> main_diag;
vector<bool> anti_diag;
vector<bool> columns;

void place(int row, int col) {
    int next_row = row + 1;
    if (next_row == board_size) {
        solutions++;
        return;
    }
    
    for (int c = 0; c < board_size; c++) {
        if (!main_diag[next_row - c + board_size] && 
            !anti_diag[next_row + c] && 
            !columns[c]) {
            main_diag[next_row - c + board_size] = anti_diag[next_row + c] = columns[c] = true;
            place(next_row, c);
            main_diag[next_row - c + board_size] = anti_diag[next_row + c] = columns[c] = false;
        }
    }
}

int main() {
    cin >> board_size;
    main_diag.resize(2 * board_size);
    anti_diag.resize(2 * board_size);
    columns.resize(board_size);
    
    for (int c = 0; c < board_size; c++) {
        main_diag[-c + board_size] = anti_diag[c] = columns[c] = true;
        place(0, c);
        main_diag[-c + board_size] = anti_diag[c] = columns[c] = false;
    }
    cout << solutions;
}

Approach 2: State Management in Current Node

#include <iostream>
#include <vector>
using namespace std;

int solutions = 0;
int board_size;
vector<bool> main_diag;
vector<bool> anti_diag;
vector<bool> columns;

void place(int row, int col) {
    int next_row = row + 1;
    if (next_row == board_size) {
        solutions++;
        return;
    }
    
    main_diag[row - col + board_size] = anti_diag[row + col] = columns[col] = true;
    for (int c = 0; c < board_size; c++) {
        if (!main_diag[next_row - c + board_size] && 
            !anti_diag[next_row + c] && 
            !columns[c]) {
            place(next_row, c);
        }
    }
    main_diag[row - col + board_size] = anti_diag[row + col] = columns[col] = false;
}

int main() {
    cin >> board_size;
    main_diag.resize(2 * board_size);
    anti_diag.resize(2 * board_size);
    columns.resize(board_size);
    
    for (int c = 0; c < board_size; c++) {
        place(0, c);
    }
    cout << solutions;
}

Approach 3: Mixed State Management

#include <iostream>
#include <vector>
using namespace std;

int solutions = 0;
int board_size;
vector<bool> main_diag;
vector<bool> anti_diag;
vector<bool> columns;

void place(int row, int col) {
    int next_row = row + 1;
    if (next_row == board_size) {
        solutions++;
        return;
    }
    
    main_diag[row - col + board_size] = anti_diag[row + col] = columns[col] = true;
    for (int c = 0; c < board_size; c++) {
        if (!main_diag[next_row - c + board_size] && 
            !anti_diag[next_row + c] && 
            !columns[c]) {
            place(next_row, c);
            main_diag[next_row - c + board_size] = anti_diag[next_row + c] = columns[c] = false;
        }
    }
}

int main() {
    cin >> board_size;
    main_diag.resize(2 * board_size);
    anti_diag.resize(2 * board_size);
    columns.resize(board_size);
    
    for (int c = 0; c < board_size; c++) {
        place(0, c);
        main_diag[-c + board_size] = anti_diag[c] = columns[c] = false;
    }
    cout << solutions;
}

Approach 4: Alternative Mixed Management

#include <iostream>
#include <vector>
using namespace std;

int solutions = 0;
int board_size;
vector<bool> main_diag;
vector<bool> anti_diag;
vector<bool> columns;

void place(int row, int col) {
    int next_row = row + 1;
    if (next_row == board_size) {
        solutions++;
        main_diag[row - col + board_size] = anti_diag[row + col] = columns[col] = false;
        return;
    }
    
    for (int c = 0; c < board_size; c++) {
        if (!main_diag[next_row - c + board_size] && 
            !anti_diag[next_row + c] && 
            !columns[c]) {
            main_diag[next_row - c + board_size] = anti_diag[next_row + c] = columns[c] = true;
            place(next_row, c);
        }
    }
    main_diag[row - col + board_size] = anti_diag[row + col] = columns[col] = false;
}

int main() {
    cin >> board_size;
    main_diag.resize(2 * board_size);
    anti_diag.resize(2 * board_size);
    columns.resize(board_size);
    
    for (int c = 0; c < board_size; c++) {
        main_diag[-c + board_size] = anti_diag[c] = columns[c] = true;
        place(0, c);
    }
    cout << solutions;
}

Approach 5: Virtual Start Node

#include <iostream>
#include <vector>
using namespace std;

int solutions = 0;
int board_size;
vector<bool> main_diag;
vector<bool> anti_diag;
vector<bool> columns;

void place(int row) {
    if (row == board_size) {
        solutions++;
        return;
    }
    
    for (int col = 0; col < board_size; col++) {
        if (!main_diag[row - col + board_size] && 
            !anti_diag[row + col] && 
            !columns[col]) {
            main_diag[row - col + board_size] = anti_diag[row + col] = columns[col] = true;
            place(row + 1);
            main_diag[row - col + board_size] = anti_diag[row + col] = columns[col] = false;
        }
    }
}

int main() {
    cin >> board_size;
    main_diag.resize(2 * board_size);
    anti_diag.resize(2 * board_size);
    columns.resize(board_size);
    
    place(0);
    cout << solutions;
}

Reconstructing Inorder Sequence from Preorder and Postorder

Given preorder and postorder traversals of a binary tree, reconstruct its inorder traversal. If a node has only one child, its considered the left child.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> pre, post;
unordered_map<int, int> post_index;
vector<int> inorder;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* build_tree(int pre_start, int pre_end, int post_start, int post_end) {
    if (pre_start > pre_end) return nullptr;
    
    Node* root = new Node;
    root->data = pre[pre_start];
    
    if (pre_start == pre_end) {
        root->left = root->right = nullptr;
        return root;
    }
    
    int left_root = pre[pre_start + 1];
    int left_end = post_index[left_root];
    int left_size = left_end - post_start + 1;
    
    root->left = build_tree(pre_start + 1, pre_start + left_size, post_start, left_end);
    root->right = build_tree(pre_start + left_size + 1, pre_end, left_end + 1, post_end - 1);
    
    return root;
}

void traverse_inorder(Node* root) {
    if (!root) return;
    traverse_inorder(root->left);
    inorder.push_back(root->data);
    traverse_inorder(root->right);
}

vector<int> reconstruct(int n, vector<int>& preorder, vector<int>& postorder) {
    pre = preorder;
    post = postorder;
    for (int i = 0; i < n; i++) {
        post_index[post[i]] = i;
    }
    
    Node* root = build_tree(0, n - 1, 0, n - 1);
    traverse_inorder(root);
    return inorder;
}

Reconstructing Preorder from Inorder and Postorder

Given inorder and postorder traversals of a binary tree, reconstruct its preorder traversal.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

string inorder, postorder;
unordered_map<char, int> inorder_index;

struct Node {
    char data;
    Node* left;
    Node* right;
};

Node* build_tree(int in_start, int in_end) {
    if (in_start > in_end) return nullptr;
    
    Node* root = new Node;
    root->data = postorder[postorder.size() - 1];
    
    if (in_start == in_end) {
        root->left = root->right = nullptr;
        return root;
    }
    
    int root_pos = inorder_index[root->data];
    
    root->right = build_tree(root_pos + 1, in_end);
    root->left = build_tree(in_start, root_pos - 1);
    
    return root;
}

void traverse_preorder(Node* root) {
    if (!root) return;
    cout << root->data;
    traverse_preorder(root->left);
    traverse_preorder(root->right);
}

int main() {
    cin >> inorder >> postorder;
    for (int i = 0; i < inorder.size(); i++) {
        inorder_index[inorder[i]] = i;
    }
    
    Node* root = build_tree(0, inorder.size() - 1);
    traverse_preorder(root);
}