Backtracking

Backtracking is an algorithmic technique used to solve problems by trying out all possible solutions and eliminating (backtracking from) the ones that don’t satisfy the problem’s conditions.

It is often described as a depth-first search (DFS) with undo:

• You explore a path (make a choice).
• If the path leads to a valid solution, keep going.
• If the path turns out to be invalid, go back (undo the choice) and try another path.

In short: Try → Check → Undo → Try Next.

When do we use Backtracking?

Backtracking is commonly used in problems where:

1. You need to generate all solutions (e.g., permutations, combinations).
2. You need to find one valid solution (e.g., Sudoku solver, N-Queens).
3. You need to optimize and stop early when an invalid choice is detected.

Backtracking Process

1. Choose – Select a possible option.
2. Explore – Recurse with the chosen option.
3. Unchoose (Backtrack) – If it doesn’t work, undo the choice and try another.

This is usually implemented with recursion.

General Template

Iterative Template of Backtracking

// Recursive backtracking function
void backtrack(vector<int>& current, vector<int>& nums, vector<vector<int>>& result) {
    // Base case: if the current solution is complete
    if (current.size() == nums.size()) {
        result.push_back(current);  // Save the solution
        return;
    }

    // Loop through all possible choices
    for (int i = 0; i < nums.size(); i++) {
        // Skip the choice if it's already used (check for duplicates, or already in the current solution)
        if (/* condition to check if nums[i] is already in current */) continue;

        // Make the choice
        current.push_back(nums[i]);

        // Recur to the next level
        backtrack(current, nums, result);

        // Undo the choice (backtrack)
        current.pop_back();
    }
}

// Driver function
vector<vector<int>> solve(vector<int>& nums) {
    vector<vector<int>> result;  // This will hold all the valid solutions
    vector<int> current;         // This holds the current solution
    backtrack(current, nums, result);
    return result;
}

Recursive Template of Backtracking

// Recursive backtracking function
void backtrack(int index, vector<int>& current, vector<int>& nums, vector<vector<int>>& result) {
    // Base case: if the current solution is complete (e.g., size equals to nums)
    if (current.size() == nums.size()) {
        result.push_back(current);  // Store the solution
        return;
    }

    // Recursive case: explore the next possible choice
    if (index >= nums.size()) {
        return;  // Base case when index exceeds the array bounds
    }

    // Option 1: Include nums[index] in the current solution
    current.push_back(nums[index]);
    backtrack(index + 1, current, nums, result);  // Recursively move to the next step

    // Option 2: Exclude nums[index] and try without it
    current.pop_back();
    backtrack(index + 1, current, nums, result);  // Recursively move to the next step
}

// Driver function
vector<vector<int>> solve(vector<int>& nums) {
    vector<vector<int>> result;  // This will hold all the valid solutions
    vector<int> current;         // This holds the current solution
    backtrack(0, current, nums, result);  // Start the recursion from the first index
    return result;
}

Example Problem of Backtracking

Generate All Binary Strings of Length n

Suppose we want to generate all possible binary strings of length n.

Step-by-Step Approach

• At each position, we have two choices: put 0 or 1.
• Place a digit and recursively move to the next position.
• If we reach length n, print the string.
• If not, backtrack and try the other option.

N-Queens

Place N queens on an N x N chessboard such that:

• No two queens attack each other.
• A queen can attack another queen in the same row, column, or diagonal.

The task: Print all possible arrangements.

Why Backtracking?

• At each row, we try placing a queen in one column.
• If it’s safe (no queen in same column or diagonal), we continue to the next row.
• If not safe, we backtrack (remove queen) and try the next column.
• If we reach row N, we found a solution.

Step-by-Step Process

1. Start with the first row.
2. For each column in that row:
   • Check if placing a queen is safe.
   • If safe → place queen and move to next row.
   • If not safe → try next column.
3. If all rows are filled, print solution.
4. If stuck, backtrack (remove queen) and try a different column.