Blog 1: Backtracking Fundamentals – The Foundation of Recursive Problem Solving

Backtracking is one of the most powerful paradigms in DSA. It is widely used in interview questions (FAANG, MAANG, Tier-1 product companies) and competitive programming to solve problems involving searching, decision-making, and constraints.

In this blog, we’ll go step by step — intuition → template → example → variations.

🔹 What is Backtracking?

At its core, backtracking is brute force + pruning.

We try out possible choices (explore).
If the choice leads to an invalid solution → undo (backtrack).
If the choice works → continue exploring deeper.

👉 Think of it as a DFS search on a decision tree.

🔹 Key Components of Backtracking

Every backtracking solution revolves around three parts:

Choices – What options do we have at this step?
Constraints – Which choices are valid? (Pruning)
Goal – When do we stop recursion?

🔹 Universal Backtracking Template (Java)

void backtrack(State state, List<Result> results) {
    if (goalReached(state)) {
        results.add(new Result(state));
        return;
    }

    for (Choice choice : validChoices(state)) {
        // 1. Make a choice
        state.make(choice);

        // 2. Explore further
        backtrack(state, results);

        // 3. Undo the choice (backtrack)
        state.undo(choice);
    }
}

✨ This template is reusable for subsets, permutations, combinations, pathfinding, puzzles, CSP problems.

🔹 Example: N-Queens (Classic Backtracking)

📌 Problem: Place N queens on an N×N chessboard such that no two queens attack each other.

Step 1: Choices

Place a queen in any column of the current row.

Step 2: Constraints

No two queens should share the same column, diagonal, or anti-diagonal.

Step 3: Goal

When all rows are filled → valid solution.

Java Code (N-Queens Solver)

import java.util.*;

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');

        backtrack(0, board, results, n);
        return results;
    }

    private void backtrack(int row, char[][] board, List<List<String>> results, int n) {
        if (row == n) {
            results.add(construct(board));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col, n)) {
                // make choice
                board[row][col] = 'Q';

                // explore
                backtrack(row + 1, board, results, n);

                // undo choice (backtrack)
                board[row][col] = '.';
            }
        }
    }

    private boolean isSafe(char[][] board, int row, int col, int n) {
        // 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 < n; i--, j++) 
            if (board[i][j] == 'Q') return false;

        return true;
    }

    private List<String> construct(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) res.add(new String(row));
        return res;
    }
}

🔹 Recursion Tree Visualization

For N=4:

Row 0 → Try placing queen at col 0..3
Row 1 → Recurse only where previous placement is safe
Row 2 → Same logic
Row 3 → If reached → add solution

The recursion explores possibilities, prunes invalid ones, and backtracks to try other paths.

🔹 Complexity Analysis

Worst-case: O(N!) (factorial explosion in permutations).
With pruning: significantly reduced search space.
Space: O(N²) for board, O(N) recursion depth.

🔹 Key Takeaways

✅ Backtracking = DFS + Undo
✅ Always define Choice, Constraint, Goal
✅ Use the universal template for different problem types
✅ Pruning makes brute force efficient enough for interviews