Backtracking

You don't need to know the right path from the start. You just need a system to explore, retreat, and try again.

Many problems can't be solved by a simple, linear algorithm. Instead, they require you to explore a vast space of possibilities, like finding every possible subset of a collection or every valid move on a chessboard. This is what backtracking is all about.

Backtracking is not a specific algorithm, but a technique. It's a methodical way of exploring a "decision tree" of choices.

Problem: Subsets (LeetCode Link): Given an integer array nums of unique elements, return all possible subsets (the power set). 💡 HintFor each number, you have two choices: either include it in your current subset or don't include it. How can you explore all combinations of these choices?

The Core Pattern: Choose, Explore, Unchoose

Think of building a solution as making a sequence of choices. Backtracking formalizes this with a recursive template:

1. Choose: Make a choice and add it to your current "path" or candidate solution.
2. Explore: Recursively call your function to explore all subsequent choices that can follow from the one you just made.
3. Unchoose: After the recursive call returns (meaning it has fully explored that branch), undo your initial choice. This is the "backtrack" step. It's what allows you to explore a completely different branch of the decision tree.

Walkthrough: Generating All Subsets

Let's apply this pattern to the "Subsets" problem. Our "decision tree" involves deciding, for each number, whether to include it in the current subset.

Our recursive function, backtrack(startIndex, currentSubset), will work as follows:

1. First, add the currentSubset to our list of all results. This captures the subset at the current state.
2. Iterate from startIndex to the end of the nums array. In each iteration, we...
   • Choose: Add nums[i] to currentSubset.
   • Explore: Recursively call backtrack(i + 1, currentSubset). We pass i + 1 to ensure we only consider numbers that appear after the current one, preventing duplicate combinations.
   • Unchoose: After the recursive call returns, currentSubset.pop(). This removes nums[i], allowing us to explore the next branch where nums[i] is not included.

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    path = []

    def backtrack(start_index):
        # Add the current subset path to the results
        result.append(path.copy())

        # Explore all choices from the current start_index
        for i in range(start_index, len(nums)):
            # 1. Choose
            path.append(nums[i])
            # 2. Explore
            backtrack(i + 1)
            # 3. Unchoose (Backtrack)
            path.pop()

    backtrack(0)
    return result

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    backtrack(0, nums, path, result);
    return result;
}

private void backtrack(int startIndex, int[] nums, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));

    for (int i = startIndex; i < nums.length; i++) {
        // 1. Choose
        path.add(nums[i]);
        // 2. Explore
        backtrack(i + 1, nums, path, result);
        // 3. Unchoose (Backtrack)
        path.remove(path.size() - 1);
    }
}

void backtrack(int startIndex, vector<int>& nums, vector<int>& path, vector<vector<int>>& result) {
    result.push_back(path);

    for (int i = startIndex; i < nums.size(); ++i) {
        // 1. Choose
        path.push_back(nums[i]);
        // 2. Explore
        backtrack(i + 1, nums, path, result);
        // 3. Unchoose (Backtrack)
        path.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    backtrack(0, nums, path, result);
    return result;
}

More Problems & Variations

The same fundamental "Choose, Explore, Unchoose" template can solve a wide range of problems with minor tweaks.

1. Combinations (LeetCode Link): Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. 💡 HintThis is almost identical to Subsets. The only change is a base case: you only add the path to your results when its size is equal to k.

2. Permutations (LeetCode Link): Given an array of distinct integers, return all possible permutations. 💡 HintThe key difference is that you can reuse elements. Your for loop should always start from 0, but you need to keep track of which numbers are already in the path to avoid duplicates. A visited set or a boolean array is perfect for this.

3. Combination Sum (LeetCode Link): Find all unique combinations of numbers that sum up to a target. 💡 HintThis adds a constraint to the "Subsets" problem. You'll need to track the currentSum and only add the path to the results if currentSum equals the target. You'll also need to prune the search (return early) if currentSum exceeds the target.

Bonus Points: Constraint Programming

Backtracking is the core engine behind a field called Constraint Programming. It's used to solve complex scheduling problems (like "What's the most efficient flight schedule given a set of planes, pilots, and routes?"), resource allocation, and classic puzzles like Sudoku or the N-Queens problem. The algorithm explores the vast tree of possible choices, but "prunes" entire branches as soon as a choice violates one of the problem's constraints.