Introduction

Backtracking is a general problem-solving technique that builds a solution incrementally and abandons (backtracks on) partial solutions as soon as they are determined to be invalid or leading nowhere. In simpler terms, it tries out different possibilities and undoes choices when a dead-end is reached, then tries another path.

This approach is commonly used for exhaustive search problems in coding interviews, especially those asking to generate all solutions (e.g. all permutations, all combinations, or all subsets of a set). Typical cues that signal a backtracking approach include phrases like “generate all possible…”, “find all combinations/permutations…”, or mentions of exploring a search space of candidates. These indicate that an exhaustive search with systematic trial-and-error (and undoing steps) is needed – which is exactly what backtracking provides.

Core Idea / Mental Model

Backtracking can be visualized as exploring a decision tree by trial and error. Each node in the tree represents a partial solution, and each branch represents a decision or choice made. The algorithm traverses this tree depth-first: choosing an option, advancing to the next decision, and so on. If it reaches a state that violates constraints or cannot lead to a complete solution (a “dead end”), it backtracks – i.e. it reverts the last choice and returns to the previous decision point to try a different option. This is analogous to navigating a maze: you make turns along a path, and if you hit a dead end, you backtrack to the last junction and take a different route.

Conceptually, backtracking is a refined brute-force search. We systematically build solutions one step at a time and abandon paths that are obviously not viable, rather than blindly exploring everything. You can think of it as a depth-first traversal of the solution space (decision tree) where at each level you make a choice, and you undo that choice when moving back up.

For example, path can represent the decisions (elements) chosen so far, and the choice set represents remaining options at that step. When a path reaches a valid end (a solution) or an invalid state, the algorithm backtracks appropriately. As one reference describes: when you reach a “bad” leaf (invalid partial solution), you revoke your most recent choice and try the next alternative; if no options remain at that node, backtrack further up. This trial-and-error with undoing ensures that eventually all valid solutions are explored without revisiting hopeless partial states.

Base Template (Python)

A backtracking solution can often be implemented with a recursive template. Below are base patterns for generating permutations and combinations.

Permutations: Backtracking Template

To generate all permutations of a list of distinct elements, we build each permutation one element at a time, using a boolean array used to mark included elements.

def permutations(nums):
    res = []                       # To store all collected permutations

    def backtrack(path):
        # Base condition: if the current permutation is complete
        if len(path) == len(nums):
            res.append(path.copy())    # record a full permutation (copy path!)
            return
        # Recursive case: try each unused option for the next position
        for i in range(len(nums)):
            if used[i]:               # skip elements already in the permutation
                continue
            # Choose: include nums[i] in the permutation
            used[i] = True
            path.append(nums[i])
            backtrack(path)           # Explore further with nums[i] chosen
            # Backtrack: undo the choice before trying the next option
            path.pop()               
            used[i] = False

    used = [False] * len(nums)        # Initialization: all elements initially unused
    backtrack([])                     # start with an empty path
    return res
# Example: permutations([1, 2, 3]) would produce:
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Initialization: Start with an empty path and used array as all False.
Base Condition: When len(path) == len(nums), a full permutation is formed. Add a copy of path to results.
Recursive Exploration: Iterate through nums. If nums[i] is not used, mark it as used, add to path, and recurse.
Backtracking Step: After recursion returns, remove the element from path and reset its used status to False.

Combinations: Backtracking Template

For combinations (subsets) of a certain length k, we use an index to ensure unique combinations and avoid reordering.

def combine(nums, k):
    res = []                         # To store all combinations of length k

    def backtrack(start, comb):
        # Base condition: if the combination has reached size k, record it
        if len(comb) == k:
            res.append(comb.copy())
            return
        # Recursive case: try adding each remaining element
        for i in range(start, len(nums)):
            comb.append(nums[i])          # Choose: include nums[i]
            backtrack(i + 1, comb)        # Explore: move to next index
            comb.pop()                    # Backtrack: remove nums[i]

    backtrack(0, [])                   # start from index 0, empty combination
    return res
# Example: combine([1, 2, 3, 4], k=2) would generate:
# [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Initialization: Start with start = 0 and an empty comb.
Base Condition: When len(comb) == k, a complete combination is formed. Add a copy to results.
Recursive Exploration: Iterate i from start to len(nums)-1. Add nums[i] to comb, then recurse with backtrack(i + 1, comb) to ensure elements are chosen in increasing order of index.
Backtracking Step: After recursion, comb.pop() to undo the choice.

Interactive Animation (Permutations of [1,2,3])

The interactive animation below demonstrates how backtracking explores the solution space for an input like [1,2,3] to find all permutations. It visually tracks the current path being built, the elements already used, and the choices made at each step. This process mirrors a depth-first traversal of a conceptual decision tree.

Follow the steps as the algorithm explores choices (example trace):

1. Start: path = [], available = [1, 2, 3] (all unused).
2. Choose 1: path = [1]. Element 1 marked as used. Recurse.
3. Choose 2: path = [1, 2]. Element 2 marked as used. Recurse.
4. Choose 3: path = [1, 2, 3]. Element 3 marked as used. Permutation found! Record [1,2,3]. Backtrack (un-choose 3, mark unused).
5. Path is [1, 2]. No more unused choices after 3. Backtrack (un-choose 2, mark unused).
6. Path is [1]. Next available unused choice is 3.
7. Choose 3: path = [1, 3]. Element 3 marked as used. Recurse... and so on.

Time & Space Complexity

Time Complexity

Backtracking algorithms often have exponential time complexity. For permutations of 𝑛 distinct elements, there are 𝑛! possible permutations. Time is O(𝑛 × 𝑛!) – 𝑛! for permutations and an extra 𝑛 factor to construct/output each. For combinations of size 𝑘 from 𝑛 elements ( (𝑛𝑘) ), time is O( (𝑛𝑘) ⋅𝑘). For all subsets (2𝑛 total), complexity is around O(2𝑛⋅𝑛).

Space Complexity

The main auxiliary space comes from the recursion stack and the temporary path/combination list, which is O(𝑛) for a recursion depth of up to 𝑛. If storing all results, output space can be exponential (e.g., O(𝑛 × 𝑛!) for permutations). Excluding output, the algorithm itself uses O(𝑛) space.

Common Pitfalls

When implementing backtracking for permutations/combinations, common pitfalls include:

By keeping these pitfalls in mind and following a clear template, you can confidently tackle permutation, combination, and subset problems using backtracking.