Backtracking

What is Backtracking?

Backtracking is a recursive algorithmic technique for solving problems by exploring all possible options. It systematically builds solutions and abandons (backtracks from) those that fail to meet the problem's constraints, making it ideal for problems that require finding all solutions or the best one.

Key Concepts in Backtracking

1. Recursive Exploration: Problems are solved by exploring decisions step by step.
2. Constraint Checking: At each step, the algorithm checks whether the current state is valid.
3. Backtracking: If the current state is invalid or does not lead to a solution, it undoes the last decision and tries a different one.

Time & Space Complexities

• Time Complexity: Highly problem-dependent; can range from O(k^n) (exponential) for n decisions with k options each, to more optimized solutions using pruning.
• Space Complexity: Depends on the recursion depth, often O(n) for problems with n levels of decisions.

When to Use Backtracking

Backtracking is commonly used for:

• Combinatorial problems (e.g., generating permutations, subsets).
• Solving constraint satisfaction problems (e.g., N-Queens, Sudoku).
• Pathfinding problems (e.g., finding all paths in a maze).
• Optimization problems when brute force can be pruned.

Code Examples

Below is an example of solving the N-Queens problem using backtracking.

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

bool isSafe(vector<string>& board, int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
        if (col - (row - i) >= 0 && board[i][col - (row - i)] == 'Q') return false;
        if (col + (row - i) < n && board[i][col + (row - i)] == 'Q') return false;
    }
    return true;
}

void solve(vector<string>& board, int row, int n, vector<vector<string>>& solutions) {
    if (row == n) {
        solutions.push_back(board);
        return;
    }

    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 'Q';
            solve(board, row + 1, n, solutions);
            board[row][col] = '.'; // Backtrack
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> solutions;
    vector<string> board(n, string(n, '.'));
    solve(board, 0, n, solutions);
    return solutions;
}

int main() {
    int n = 4;
    vector<vector<string>> solutions = solveNQueens(n);

    for (const auto& solution : solutions) {
        for (const auto& row : solution) {
            cout << row << endl;
        }
        cout << endl;
    }

    return 0;
}

Problems to Solve

Important Problems on Backtracking

Backtracking [NeetCode]

Resources

• Backtracking by Aditya Verma