Backtracking Pattern

The Backtracking pattern is a trial-and-error search technique that incrementally builds candidate solutions, abandoning a path (backtracking) as soon as it determines the path cannot lead to a valid final solution.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem asks you to generate “all permutations”, “all combinations”, “all subsets”, or “all possible paths”.
• The constraints are extremely small (e.g. n <= 15 or n <= 20), which is a major signal that an exponential-time search is expected.
• You must explore multiple choices at each step, and making one choice restricts future choices.

How It Works

Backtracking behaves like a depth-first traversal of a decision tree. At each level of recursion:

• Base Case: Check if the current state forms a complete, valid solution. If so, record it and return.
• Prune Check: Check if the current path already violates constraints. If so, return immediately (pruning the branch).
• Decisions: Iterate through all choices available at the current state.
  • Make Choice: Add the choice to the path and update the state.
  • Recurse: Call the helper function to explore the subsequent choices.
  • Undo Choice: Remove the choice from the path and restore the state (backtrack).

For example, to find all subsets of [1, 2]:

1. Root of decision tree: start with current = [].
2. Decision 1 (for 1): Include it. current = [1].
   • Decision 2 (for 2): Include it. current = [1, 2]. End of array. Record [1, 2]. Backtrack to [1].
   • Decision 3 (for 2): Exclude it. current = [1]. End of array. Record [1]. Backtrack to [].
3. Decision 4 (for 1): Exclude it. current = [].
   • Decision 5 (for 2): Include it. current = [2]. End of array. Record [2]. Backtrack to [].
   • Decision 6 (for 2): Exclude it. current = []. End of array. Record [].
4. Output: [[1, 2], [1], [2], []].

Complexity, With Caveats

• Time Complexity: O(k^N) where k is the branching factor (choices at each step) and N is the depth of the decision tree. For example, permutations run in O(N!) time; subsets run in O(2^N) time.
• Space Complexity: O(N) representing the recursion stack depth and the active path list size.

Minimal Code Template

import java.util.ArrayList;
import java.util.List;

public class BacktrackingTemplate {
    // Find All Subsets
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(0, nums, new ArrayList<>(), result);
        return result;
    }

    private void dfs(int index, int[] nums, List<Integer> current, List<List<Integer>> result) {
        if (index == nums.length) {
            result.add(new ArrayList<>(current)); // record copy of active path
            return;
        }

        // Choice 1: include nums[index]
        current.add(nums[index]);
        dfs(index + 1, nums, current, result);
        current.remove(current.size() - 1); // backtrack (undo choice)

        // Choice 2: exclude nums[index]
        dfs(index + 1, nums, current, result);
    }
}

# Find All Subsets
def subsets(nums: list[int]) -> list[list[int]]:
    result = []

    def dfs(index, current):
        if index == len(nums):
            result.append(list(current))  # record copy of active path
            return

        # Choice 1: include nums[index]
        current.append(nums[index])
        dfs(index + 1, current)
        current.pop()  # backtrack (undo choice)

        # Choice 2: exclude nums[index]
        dfs(index + 1, current)

    dfs(0, [])
    return result

#include <vector>

class BacktrackingTemplate {
private:
    void dfs(int index, const std::vector<int>& nums, std::vector<int>& current, 
             std::vector<std::vector<int>>& result) {
        if (index == nums.size()) {
            result.push_back(current); // record copy
            return;
        }

        // Choice 1: include nums[index]
        current.push_back(nums[index]);
        dfs(index + 1, nums, current, result);
        current.pop_back(); // backtrack (undo choice)

        // Choice 2: exclude nums[index]
        dfs(index + 1, nums, current, result);
    }

public:
    std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        dfs(0, nums, current, result);
        return result;
    }
};

Where This Pattern Falls Short

• Optimization problems with large inputs: If you need to find the single best value (e.g. shortest path or maximum sum) and n is large (e.g. n > 50), backtracking will time out due to its exponential time complexity. You must use Dynamic Programming or Greedy algorithms instead.
• No overlapping subproblems: If the decision tree visits identical states multiple times, a naive backtracking search will perform redundant calculations. You must add memoization to cache results, transforming the search into top-down Dynamic Programming.

Related Patterns, Compared

• Dynamic Programming: choose this instead when you only need to calculate an optimal value (maximum, minimum, count) rather than generating the actual paths, allowing you to use caches to resolve overlapping states in polynomial time.
• Graphs: choose this instead when the decision paths are represented by an explicit network of nodes and edges, using visited maps to avoid loops.

Frequently Asked Questions

Why must we copy the path list before adding it to the result? Because the path variable current is passed by reference and mutated throughout the execution. If you add the reference directly, future backtrack calls will clear its elements, leaving you with a list of empty arrays. You must add a snapshot/clone of the list.

What does pruning mean in backtracking? Pruning means returning early from a recursive branch when you determine that the current path already violates constraints (e.g. the current sum exceeds the target). This prevents the search from visiting thousands of child states.

What does this pattern test in interviews? It tests your ability to model decision states as trees, manage recursion frames, and execute cleanup/restoration steps during backtracks.