Backtracking is the technique of trying a choice, recognizing it does not work, and undoing it to try a different choice. It applies to problems that involve building a solution through a sequence of decisions.

Common applications include generating combinations, solving puzzles like Sudoku, finding paths in a maze, and a wide range of coding interview problems.

Instead of randomly guessing, backtracking explores all possibilities in an organized way while pruning paths that cannot lead to valid solutions.

Backtracking is a structured 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.

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.

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:

Every backtracking solution follows the same basic structure. The template below applies to most backtracking problems.

Each component is described below.

The Three Steps: Choose, Explore, Unchoose

At each decision point:

The choose/unchoose pattern lets backtracking share a single mutable candidate buffer across the entire search. Each branch mutates the buffer, explores, then restores it before returning, so the next branch starts from a clean state without allocating new memory per call.

Base Case

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

Pruning

Pruning means skipping branches that cannot lead to valid solutions. You can prune:

Effective pruning can significantly reduce the number of branches explored.

Here is a complete example that is different from the LeetCode problems we will cover later.

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

Here is a trace through a 2x2 grid:

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.

The grid-paths example shows the choose-explore-unchoose mechanics, but it is structurally weak: every partial path can extend to a valid solution, so no branch ever gets pruned and the algorithm degenerates to plain enumeration. The next example shows backtracking on a problem where the choose-unchoose pattern carries real weight.

Problem: Given an array of distinct integers nums, return all possible subsets (the power set). For nums = [1, 2, 3], the output has 2^n = 8 subsets: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

Decision Tree

At each position, we decide whether to extend the current subset with the next available element. Every node in the tree is itself a valid subset, so we record the current state at every recursion entry rather than only at leaves.

The start index in the code below enforces the rule "only consider elements to the right of the last one picked," which is what keeps the tree from generating [2, 1] as a duplicate of [1, 2].

Code

Trace for [1, 2, 3]

The same current list is mutated and restored across the entire search. The table below shows the state of current at each recursive call and what gets pushed to result.

Final result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]].

The current ArrayList is the same object the entire time. Each recursive call appends one element, recurses, then pops it. The deep copy happens only at the moment a subset is added to result. This is the standard way to avoid all stored subsets pointing at the same mutating buffer.

Complexity

When the input contains duplicate values, naive backtracking produces duplicate solutions. For Subsets II with nums = [1, 2, 2], the algorithm above would generate [2] twice (once using the element at index 1, once using the element at index 2) and [1, 2] twice for the same reason. The output is supposed to be a set of unique subsets, so these repeats are bugs.

The Fix: Sort, Then Skip Duplicates at the Same Depth

Two changes turn the subsets template into a correct Subsets II solution:

Why i > start and Not i > 0

The guard i > start reads as "we are picking a duplicate value at the same recursion depth as a previous sibling choice." That is the case that produces a redundant subtree. The first occurrence of a duplicate at any depth (i == start) is still allowed, because that is the only path that ever includes this value at this position. Subsequent occurrences at the same depth would recreate an identical subtree under a different sibling, so we skip them.

Using i > 0 instead would also skip the case where two equal values appear in the same subset, which is a different problem entirely. With nums = [2, 2], the valid subset [2, 2] would never get generated because the second 2 would be skipped at depth 1.

Variant: Permutations II

For Permutations II, sorting and the same-depth skip rule still apply, but the bookkeeping is different because permutations care about position rather than left-to-right index order. The standard approach uses a used[] boolean array that tracks which input positions are already in the current permutation.

The skip condition becomes if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue. This says: if the previous equal value has not yet been placed, skip this one. The reasoning is that we always place duplicates in their original left-to-right order. If nums[i - 1] is still unused, then placing nums[i] first would generate the same permutation we would build by placing nums[i - 1] first, just by a different recursion path.

Backtracking problems fall into three flavors based on what the problem asks for. Recognizing which flavor a problem is shapes the code structure.

1. Enumerate All Solutions

Examples: Subsets, Permutations, Combinations, Combination Sum, Palindrome Partitioning.

Accumulate every valid solution into a result list. The recursive function returns void. The full search tree is traversed (modulo pruning). This is the pattern used in every example so far in this chapter.

2. Find One Solution and Stop

Examples: Sudoku Solver, single-solution N-Queens, Word Search, "is there a valid configuration."

Return a boolean from the recursive function. The moment a branch succeeds, propagate true upward to short-circuit the rest of the search. The choose-explore-unchoose structure stays the same, but the explore step checks the return value and bails out immediately on success.

The undo on failure still matters, because the caller may try a different choice. The short-circuit on success matters because exploring the rest of the tree would be wasted work.

3. Count Solutions

Examples: Count of Valid Configurations, Number of Distinct Subsequences, counting variants of permutation and combination problems.

Return an integer from the recursive function and sum the counts across recursive calls. The choose-unchoose pattern still applies, but no result list is maintained.

Counting variants often have overlapping subproblems on the partial-state signature. When the count depends only on a small piece of state (current index, remaining target, etc.) and not on the full history, the recursion can be memoized, which converts the backtracking solution into a top-down DP.

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.

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.