Imagine you are solving a maze. You walk down a path, hit a dead end, turn around, and try a different route. This simple idea, trying something, realizing it does not work, and undoing your choice to try something else, is the essence of backtracking.

Backtracking is one of the most powerful algorithmic techniques for solving problems that involve making a sequence of decisions. It shows up everywhere: generating all possible combinations, solving puzzles like Sudoku, finding paths in a maze, and countless coding interview problems.

What makes backtracking special is its systematic approach. Instead of randomly guessing, it explores all possibilities in an organized way while pruning paths that cannot lead to valid solutions. Master this technique, and you will unlock a whole class of problems that seem impossibly complex at first glance.

What Is Backtracking?

Backtracking is a refined form of brute force. It tries to build a solution incrementally, one piece at a time, and abandons a path as soon as it determines that the path cannot lead to a valid solution.

Think of it like this: you are filling out a form with multiple fields. You fill in the first field, then the second, then the third. But when you reach the fourth field, you realize there is no valid option given your previous choices. Instead of starting over from scratch, you go back to the third field, try a different value there, and continue forward again.

The key insight is: backtracking explores the solution space as a decision tree, where each node represents a partial solution, and branches represent the choices available at that point.

This tree shows all permutations of [1, 2, 3]. Each path from root to leaf represents one complete solution. Backtracking traverses this tree using depth-first search, building solutions one choice at a time.

When to Use Backtracking

Backtracking is the right tool when your problem has these characteristics:

1. You need to find all possible solutions (or one valid solution)

Problems that ask for "all combinations," "all permutations," "all valid configurations," or "find any valid solution" are prime candidates.

2. The solution is built incrementally through a series of choices

At each step, you make a decision from a set of options. The sequence of decisions leads to a complete solution.

3. Some choices can be ruled out early

If you can detect that a partial solution cannot possibly lead to a valid complete solution, you can prune that branch and save computation.

4. The problem has constraints that must be satisfied

Constraints help you determine when to backtrack. If a choice violates a constraint, you know to undo it immediately.

Here are common problem types where backtracking excels:

The Backtracking Template

Every backtracking solution follows the same fundamental structure. Once you internalize this template, you can apply it to any backtracking problem.

Let us break down each component:

The Three Steps: Choose, Explore, Unchoose

This is the heart of backtracking. At each decision point:

The "unchoose" step is what makes backtracking different from regular recursion. You are explicitly reverting your state so you can try a different choice.

Base Case

The base case defines when you have built a complete solution. This could be:

Pruning

The real power of backtracking comes from pruning, skipping branches that cannot lead to valid solutions. You can prune:

Effective pruning can reduce exponential time complexity to something manageable.

Example Walkthrough: Finding All Paths in a Grid

Let us work through a complete example that is different from the LeetCode problems we will cover later. This will solidify your understanding of the template.

Problem: Given an m x n grid, find all paths from the top-left corner to the bottom-right corner. You can only move right or down.

Step 1: Identify the Components

Step 2: Apply the Template

Step 3: Trace the Execution

Let us trace through a 2x2 grid to see backtracking in action:

Notice how after each recursive call, we remove the last cell from the path (UNCHOOSE). This restores the state so we can try the alternative direction.

Visualizing the Decision Tree

Each leaf node that reaches the goal is a valid path. Backtracking systematically explores every branch of this tree.

Backtracking vs. Other Techniques

Understanding when to use backtracking versus other approaches helps you pick the right tool.

Backtracking vs. Dynamic Programming

If you need to enumerate all solutions, use backtracking. If you need to count or find the optimal solution, consider dynamic programming.

Backtracking vs. BFS

If you need the shortest path or minimum steps, BFS is usually better. If you need all paths or the problem has deep solutions, backtracking works well.

Backtracking vs. Greedy

Greedy makes the locally optimal choice and never reconsiders. Backtracking explores all possibilities. Use greedy only when you can prove it leads to the global optimum.

Time and Space Complexity

Backtracking algorithms typically have exponential time complexity because they explore a tree of possibilities.

Time Complexity Patterns

The actual runtime depends heavily on how effectively you can prune. A well-pruned backtracking solution can be orders of magnitude faster than the worst case.

Space Complexity

Space complexity in backtracking comes from two sources:

For most problems, the space is O(n) for the recursion stack plus the space needed to store the current partial solution.