I am Harisai

Backtracking is a powerful algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, and removing those pieces that fail to satisfy the constraints of the problem at any point in time.

🔙Core Idea

Backtracking is essentially a refined Brute Force search. Think of it like navigating a Maze 🧩.

When you reach a fork in the road:

1. You pick a path and follow it.
2. If you hit a dead end, you “backtrack” to the last fork.
3. You try the next available path.

Instead of looking at every single possible combination (Brute Force), Backtracking “prunes” the search. If it realizes a certain path can’t possibly lead to a solution, it stops immediately and turns back, saving a massive amount of time.

⚙️ The Three Pillars of Backtracking

To solve any backtracking problem, you need to identify three things:

1. Choice: What is the next move you can make? (e.g., Which number can I place in this Sudoku cell?)
2. Constraints: Is this move allowed? (e.g., Is this number already in the same row or column?)
3. Goal: When are we finished? (e.g., Are all cells filled correctly?)

🧩 Real-World Examples

Example 1: ♟️ The N-Queens Problem

How do you place 8 queens on a chessboard so that no two queens attack each other?

• Action: Place a queen in the first row.
• Backtrack: If you reach the third row and find there is no safe spot left, you go back to the second row and move that queen to a different position.

Example 2: 🔐 Cracking a Combination Lock

If you forgot your 3-digit code:

• You try 0-0-0, 0-0-1, 0-0-2.
• If “0-0” doesn’t work with any third digit, you “backtrack” and change the second digit to “1” (0-1-0).

Example 3: 🗺️ Map Coloring

Assigning colors to different regions on a map so that no two adjacent regions have the same color.

• If you run out of colors for a specific country, you go back to the previous country and change its color to see if it opens up a new possibility.

🏗️ General Template (Pseudo-code)

Most backtracking problems follow this identical structural pattern:

function backtrack(currentPath) {
    // 1. Goal Check
    if (goalReached) {
        result.push([...currentPath]);
        return;
    }

    for (let choice of allChoices) {
        // 2. Constraint Check
        if (isValid(choice)) {
            // 3. Make Choice
            currentPath.push(choice);

            // 4. Recurse
            backtrack(currentPath);

            // 5. Undo Choice (The "Backtrack" step)
            currentPath.pop();
        }
    }
}

🏁 Backtracking vs. Recursion

It is common to confuse the two.

• Recursion is a tool (a function calling itself).
• Backtracking is a strategy that uses recursion to explore and discard invalid options.

⏱️ Complexity Analysis

• Time: Usually exponential (e.g., O(2^N) or O(N!)). Because we are exploring combinations, the numbers grow very fast.
• Space: O(N), which is typically the depth of the recursion tree (how many choices we have to make to reach the goal).

💬 What’s Next?

Backtracking can be intimidating at first, but once you master the “Choice, Constraint, Goal” framework, you can solve some of the toughest coding interview problems out there. Let’s look at and solve some LeetCode problems.