Backtracking

Introduction

In our search for optimal solutions, we looked at Dynamic Programming, which caches sub-problem results, and Greedy Algorithms, which blindly makes the best immediate choice.

But what if a problem asks you to generate all possible combinations? What if you need to solve a Sudoku puzzle, where placing a 9 might seem valid now, but causes a contradiction 30 steps later?

You need an algorithm that can explore a path, realise it made a mistake, undo its actions, and try an alternative. You need Backtracking.

What is Backtracking?

Backtracking is fundamentally a Depth-First Search (DFS) applied to an abstract “decision tree.”

Imagine packing a suitcase. You add a shirt (Choice 1). You add shoes (Choice 2). You try to add a jacket (Choice 3), but it doesn’t fit. You don’t throw away the whole suitcase! You simply take out the shoes (undo Choice 2), and try to put the jacket in again.

The magic of Backtracking lies in maintaining a single shared state (like a List or a Board) and modifying it as you go deeper into the recursion, then reverting those modifications as you come back up.

The Universal Backtracking Template

Almost every Backtracking problem in existence can be solved using this exact template. Memorise it!

private void backtrack(List<List<Integer>> result, List<Integer> currentPath, int[] choices) {
    // 1. Base Case: Have we reached a valid solution?
    if (isValidSolution(currentPath)) {
        result.add(new ArrayList<>(currentPath)); // ADD A COPY!
        return; // stop exploring this path
    }

    // 2. Iterate through all possible choices from this state
    for (int choice : choices) {
        
        // Optimisation: Pruning (Skip invalid choices early)
        if (!isValidChoice(choice, currentPath)) {
            continue; 
        }

        // 3. DO: Make the choice
        currentPath.add(choice);

        // 4. RECURSE: Explore further down this path
        backtrack(result, currentPath, choices);

        // 5. UNDO: Revert the choice to explore a different option
        currentPath.remove(currentPath.size() - 1);
    }
}

Crucial Detail: Notice new ArrayList<>(currentPath). Because currentPath is constantly being modified (added to and removed from), if you just add the reference result.add(currentPath), all your results will end up totally empty by the end of the algorithm! You must take a snapshot (a copy).

Classic Example: Generating Permutations

Problem: Given an array [1, 2, 3], generate all possible ordering permutations (e.g. [1,2,3], [1,3,2], [2,1,3]...).

Let’s apply our template.

import java.util.*;

public class Permutations {
    
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums) {
        // Base Case: If our path size matches nums length, we have a full permutation
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int num : nums) {
            // Pruning: Permutations can't have duplicate identical numbers
            if (path.contains(num)) {
                continue; 
            }

            // DO
            path.add(num);
            
            // RECURSE
            backtrack(result, path, nums);
            
            // UNDO
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3};
        System.out.println(permute(data));
        // Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    }
}

The Recursion Tree for [1,2,3]

1. Path: []. Loop picks 1. Path becomes [1]. Recurse.
2. Path: [1]. Loop skips 1 (pruned). Picks 2. Path becomes [1, 2]. Recurse.
3. Path: [1, 2]. Loop skips 1, skips 2. Picks 3. Path becomes [1, 2, 3]. Recurse.
4. Path: [1, 2, 3]. Size == 3. Save copy to result. Return to step 3.
5. Path [1, 2, 3]. Loop finishes. Undo 3. Path becomes [1, 2]. Return to step 2.
6. Path [1, 2]. Loop finishes. Undo 2. Path becomes [1]. Loop picks 3. Path becomes [1, 3]…

Complexity of Backtracking

Backtracking generates combinations, which means it scales factorially or exponentially.

• Permutations: $O(N!)$
• Subsets: $O(2^N)$

You should only use Backtracking when $N$ is very small (usually $N \le 20$). If $N$ is large, you are missing a DP or Greedy optimisation.

Practice Problems

Every single one of these problems is solved using the exact template above.

1. Subsets – LeetCode #78 — Generate all combinations (Power Set).
2. Combination Sum – LeetCode #39 — A variation where you can reuse exactly the same choices multiple times.
3. N-Queens – LeetCode #51 — The boss battle of Backtracking. Place N queens on a chess board so they can’t attack each other.

What’s Next?

Backtracking requires a solid grasp of recursion. In fact, so do Binary Trees, DFS, and Divide-and-Conquer algorithms!

If you are still struggling to trace how functions call themselves and pass variables back up the chain, our next post will break down the fundamental patterns of recursion: Recursion Patterns — Base Cases & Unwinding.