Backtracking

How does Backtracking work?

Keep one array holding the choices made so far. It is the path down the tree.

At each level, loop over the options still available. Every option is one branch.

Push the option, then call yourself for the next level. Nothing else changes.

When that call returns, pop the option off again. The array is exactly as it was.

At the bottom, record a copy of the path. Recording the array itself stores a shared buffer.

Cut a branch as soon as it cannot work. That pruning is where the speed comes from.

Sources: Wikipedia: Backtracking

1. path = []Listing the subsets of [1, 2]. The empty set already counts.
2. path = [1]Take the 1 and go one level down.
3. path = [1, 2]Take the 2 as well. This branch is finished.
4. path = [1], then []Two pops undo both choices. The array is empty again.
5. path = [2]Skip the 1 and take the 2. Four subsets in total.

function backtrack(path, choices, result) {
    if (path.length === choices.length) { // or another stop condition
        result.push([...path]);
        return;
    }
    for (const choice of choices) {
        path.push(choice); // choose
        backtrack(path, choices, result); // explore
        path.pop(); // undo
    }
}

function backtrack(path: number[], choices: number[], result: number[][]): void {
    if (path.length === choices.length) { // or another stop condition
        result.push([...path]);
        return;
    }
    for (const choice of choices) {
        path.push(choice); // choose
        backtrack(path, choices, result); // explore
        path.pop(); // undo
    }
}

def backtrack(path, choices, result):
    if len(path) == len(choices):  # or another stop condition
        result.append(path[:])
        return
    for choice in choices:
        path.append(choice)  # choose
        backtrack(path, choices, result)  # explore
        path.pop()  # undo

function backtrack(array &$path, array $choices, array &$result): void {
    if (count($path) === count($choices)) {
        $result[] = $path;
        return;
    }
    foreach ($choices as $choice) {
        $path[] = $choice; // choose
        backtrack($path, $choices, $result); // explore
        array_pop($path); // undo
    }
}

    public static void backtrack(List<Integer> path, int[] choices, List<List<Integer>> result) {
        if (path.size() == choices.length) { // or another stop condition
            result.add(new ArrayList<>(path));
            return;
        }
        for (int choice : choices) {
            path.add(choice); // choose
            backtrack(path, choices, result); // explore
            path.remove(path.size() - 1); // undo
        }
    }

    public static void Backtrack(List<int> path, int[] choices, List<List<int>> result) {
        if (path.Count == choices.Length) { // or another stop condition
            result.Add(new List<int>(path));
            return;
        }
        foreach (int choice in choices) {
            path.Add(choice); // choose
            Backtrack(path, choices, result); // explore
            path.RemoveAt(path.Count - 1); // undo
        }
    }

A worked example of Backtracking

Every combination that hits a target

You get distinct positive numbers and a target. List every combination that adds up to it.

A number may be used as many times as you like.

At each level, try every number from the current index onward.

Starting at the current index stops the same combination appearing reordered. A negative remainder cuts the branch.

function combinationSum(candidates, target) {
    const result = [];
    const path = [];

    function walk(start, left) {
        if (left === 0) {
            result.push([...path]); // a copy, never the live array
            return;
        }
        if (left < 0) return; // pruned: this branch cannot recover

        for (let i = start; i < candidates.length; i++) {
            path.push(candidates[i]);
            walk(i, left - candidates[i]); // i, not i + 1: reuse is allowed
            path.pop();                    // undo before the next option
        }
    }

    walk(0, target);
    return result;
}

When should you use Backtracking?

Use Backtracking when the problem statement says “generate all subsets/permutations/combinations”, “n is small (roughly n <= 12-20), exponential search is acceptable” or “make a choice, recurse, then undo it before trying the next choice”. A solution built on it usually runs in O(2^n)/O(n!).

• •generate all subsets/permutations/combinations
• •n is small (roughly n <= 12-20), exponential search is acceptable
• •make a choice, recurse, then undo it before trying the next choice
• •place items under constraints and back off on conflict (N-Queens, Sudoku)
• •return every valid arrangement, not just one

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Backtracking confused with?

Backtracking is most often confused with Recursion, Recursion with memoization, Dynamic programming (1-D) and Matrix word search (grid DFS/backtracking).

• Recursion: Recursion goes down and comes back. Backtracking also puts the state back as it returns.
• Recursion with memoization: A cache pays off when arguments repeat. Down a path of distinct choices they rarely do.
• Dynamic programming (1-D): DP counts or optimises without listing anything. Backtracking is for when you need the arrangements.
• Matrix word search (grid DFS/backtracking): That is this pattern on a grid. The choice there is which neighbour to step into.

Common mistakes with Backtracking

• Storing the live path in the results

  Every result then points at the same array. Push a copy of it instead.

• Forgetting to undo the choice

  The path grows and never shrinks. Later branches then inherit choices that were not theirs.

• Starting the inner loop at zero

  The same combination then appears in every possible order. Pass the current index down.

• Never pruning a branch

  Without an early exit the entire tree gets explored. Most of these are only fast because of the cut.

Which interview problems use Backtracking?

Interview problems solved with Backtracking include Subsets, Permutations, Combination sum, N-queens, Word search, Palindrome partitioning and Sudoku solver.

• Subsets: Two options per element: take it or skip it.
• Permutations: Every unused element is an option at each level.
• Combination sum: The index passed down decides whether reuse is allowed.
• N-queens: Prune on the column and on both diagonals.
• Word search: The grid is the tree, and neighbours are the choices.
• Palindrome partitioning: Cut at every position whose prefix is a palindrome.
• Sudoku solver: Nine options per empty cell, pruned by the rules.

What is the time and space complexity of Backtracking?

The target complexity of Backtracking is O(2n)/O(n!).

The output is exponential, so n stays small. Subsets of 20 items are 1e6, permutations of 10 are 3.6e6.