Backtracking often feels like magic when you see it in a textbook—that recursive function that just "finds the answer." But in practice, it's really just a systematic way of admitting you were wrong and retracing your steps. I want to show you how this actually evolves in code, because the "pattern" isn't something you memorize; it's a strategy for managing state.

Tackling a simple grid escape

Let's say we have a small grid. Some cells are walls (1), some are open (0), and we need to get from the top-left to the bottom-right. I'll start with a naive recursive approach. I'll just try moving right or down. If I hit the target, I'm done.

bool findPath(int x, int y, vector<vector<int>>>& grid) {
    if (x == grid.size() - 1 && y == grid[0].size() - 1) return true;
    if (x >= grid.size() || y >= grid[0].size() || grid[x][y] == 1) return false;

    if (findPath(x + 1, y, grid) || findPath(x, y + 1, grid)) {
        return true;
    }
    return false;
}

This works for a simple "right and down" movement. But what if the path winds? What if I need to move up or left to go around a wall? If I add findPath(x - 1, y) and findPath(x, y - 1) to that list, the program immediately crashes with a stack overflow. I've created an infinite loop: the code moves right, then left, then right, then left, forever.

The state tracking trap

To fix the loop, the obvious move is to mark where I've been. I'll create a visited matrix. If I've been to a cell, I won't go back. It seems straightforward.

bool findPath(int x, int y, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
    if (x == grid.size() - 1 && y == grid[0].size() - 1) return true;
    if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || 
        grid[x][y] == 1 || visited[x][y]) return false;

    visited[x][y] = true; // Mark this spot

    if (findPath(x + 1, y, grid, visited) || 
        findPath(x - 1, y, grid, visited) || 
        findPath(x, y + 1, grid, visited) || 
        findPath(x, y - 1, grid, visited)) {
        return true;
    }
    return false;
}

Now the stack overflow is gone, but I've hit a different problem. I'm finding that the algorithm fails to find paths that actually exist. Why? Because my visited array is persistent. If the algorithm explores a "dead end" path, it marks all those cells as visited. When the recursion unwinds and tries a different path that happens to need one of those cells, it sees the true in the visited array and thinks, "Nope, already been there," even though that cell isn't part of the current path.

The "Undo" realization

This is the core of backtracking. The visited status shouldn't mean "I have ever been here in the entire history of the program." It should mean "I am currently using this cell in my current attempt to reach the goal."

If a path fails, I need to "clean up" after myself. I have to unmark the cell as I retreat back up the recursion tree. This allows other potential paths to try that cell again.

bool findPath(int x, int y, vector<vector<int>>& grid, vector<vector<bool>>& visited) {
    if (x == grid.size() - 1 && y == grid[0].size() - 1) return true;
    if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || 
        grid[x][y] == 1 || visited[x][y]) return false;

    visited[x][y] = true; // Choose: Mark as part of the current path

    if (findPath(x + 1, y, grid, visited) || 
        findPath(x - 1, y, grid, visited) || 
        findPath(x, y + 1, grid, visited) || 
        findPath(x, y - 1, grid, visited)) {
        return true; 
    }

    // Backtrack: "I've tried every option from here and none worked."
    // Unmark this spot so other paths can potentially use it.
    visited[x][y] = false; 
    return false;
}

Recognizing the pattern

Look at what we just did. This is the universal backtracking template. Whether you're solving a Sudoku, the N-Queens problem, or generating permutations, the logic is always this:

• Choose: Update your state (mark a cell, add a number to a list, move a piece).
• Explore: Recurse to see if that choice leads to a solution.
• Un-choose: Revert the state change. This is the "backtrack" step.

The most common bug I see in C++ backtracking is forgetting the "Un-choose" step, especially when passing containers by reference. Since we pass visited by reference for efficiency (to avoid copying a huge matrix every call), we are responsible for returning it to its original state before the function returns.

📋 Practical Task

Exercise: The Restricted Sum-Set Finder

You need to write a function that finds all unique combinations of numbers from a given set that add up to a specific target value. However, there's a catch: you can use each number from the set only once, and the resulting combinations must be sorted to avoid duplicates.

Requirements:

• Implement a function void findCombinations(int index, int target, vector<int>& candidates, vector<int>& current, vector<vector<int>>& results).
• Use the backtracking pattern: Choose (add number to current), Explore (recurse with updated target), and Un-choose (remove number from current).
• Ensure that if the input candidates are {10, 1, 2, 7, 6, 1, 5} and the target is 8, your code handles the duplicate '1's without producing duplicate combinations in the final result.