Backtracking Explained

Backtracking is a problem-solving technique built on top of recursion: try a choice, recurse forward as if it was correct, and if it later turns out to be a dead end, undo that choice and try the next one. It's essentially a smart, systematic form of trial and error — instead of blindly trying every possible combination, backtracking abandons a path the moment it becomes clear it can't lead to a valid solution, which saves enormous amounts of wasted work.

You'll recognize a backtracking problem by its shape: you're building up a solution piece by piece (a path, a sequence, a placement on a board), and at each step there are several choices, only some of which lead somewhere valid.

The Core Pattern

Every backtracking solution follows the same skeleton: make a choice, recurse, then undo the choice ("backtrack") before trying the next option. Here's that pattern generating all permutations of a short list — a classic backtracking problem:

def permute(nums, current, used, results):
    # Base case: a full-length permutation is complete
    if len(current) == len(nums):
        results.append(current[:])
        return

    for i in range(len(nums)):
        if used[i]:
            continue

        # 1. Make a choice
        current.append(nums[i])
        used[i] = True

        # 2. Recurse forward as if this choice is correct
        permute(nums, current, used, results)

        # 3. Undo the choice (backtrack) before trying the next option
        current.pop()
        used[i] = False

results = []
permute([1, 2, 3], [], [False, False, False], results)
print(results)

Output:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

The "undo" step — current.pop() and resetting used[i] — is what makes this backtracking rather than plain recursion. Without it, the algorithm couldn't try a fresh set of choices on the next loop iteration, because the previous choice would still be lingering in current. See a complete, interview-ready version of this in our Python permutations program.

Pruning: Backtracking's Real Superpower

The real efficiency gain comes from pruning — checking a constraint early and abandoning a branch the instant it's violated, instead of building the entire invalid solution first. The N-Queens problem is the textbook example: instead of placing all N queens and then checking if the board is valid, you check after placing each queen whether it attacks any previously placed queen, and backtrack immediately if it does. This prunes away huge swaths of the search space that would obviously never work. Our N-Queens solution shows this pruning in action.

When Backtracking Is the Right Tool

Reach for backtracking when a problem asks you to find all valid arrangements/combinations/paths that satisfy some constraint, or to determine if at least one valid solution exists — generating permutations or combinations, solving constraint puzzles (N-Queens, Sudoku), finding paths through a maze, or partitioning a set under some rule. Its worst-case time complexity is often exponential, since in the absolute worst case it still explores a tree of possibilities — but effective pruning is what keeps it fast enough to be useful in practice, which is why a good backtracking solution always asks "can I detect failure earlier?"

---