Backtracking Basics

Every backtracking problem is a sequence of decisions. Draw them as a tree:

• the root is the empty starting state, with nothing chosen yet;
• each branch is one choice;
• each path from the root is a partial solution;
• a leaf is either a complete solution or a dead end.

For "all subsets of [1, 2, 3]", each level decides which number to add next, and only numbers after the last one chosen are allowed, so no subset appears twice:

The algorithm visits this tree depth-first: it goes all the way down one branch before trying the next. Here every node is a valid subset, so all 8 are recorded.

Walking the tree uses one recursive function with three moves inside a loop over the options:

1. Choose: add an option to the current partial solution.
2. Explore: call the function again to build the rest.
3. Un-choose: remove that option again, so the next option starts from the same state.

The un-choose step is what gives backtracking its name. Without it, the choices from one branch would leak into the next one.

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

public class Template {

    // All subsets of nums: the smallest complete backtracking program
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int start, List<Integer> current,
                                  List<List<Integer>> result) {
        result.add(new ArrayList<>(current));      // record the current state (a copy)

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);                  // 1. choose
            backtrack(nums, i + 1, current, result);   // 2. explore
            current.remove(current.size() - 1);    // 3. un-choose
        }
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[] {1, 2, 3}));
        // [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    }
}

Two details trip people up:

• Save a copy. result.add(new ArrayList<>(current)), not result.add(current). There is only one current list; without the copy, every saved result would be the same list, and it ends up empty.
• Undo exactly what you did. If you added to a list, remove from it; if you marked a cell as used, unmark it.

To adapt the template to a new problem, decide:

Backtracking explores a tree that can be huge, so the main way to make it fast is to stop going down a branch as soon as it cannot lead to a solution. This is called pruning.

• Check validity before recursing. N-Queens checks that a square is safe before placing a queen, instead of placing all queens and checking at the end.
• Sort and stop early. In Combination Sum, once a sorted candidate is larger than the remaining target, every later candidate is too, so the loop can break.
• Bound the answer. In Fair Distribution of Cookies, a branch whose largest share is already worse than the best answer found so far is abandoned.
• Count what is left. In Restore IP Addresses, if the remaining digits cannot fill the remaining parts (each needs 1 to 3 digits), stop.

Good pruning does not change the worst-case complexity, but in practice it often cuts the work by orders of magnitude.

When the input contains equal values, such as [1, 2, 2], the plain template produces the same subset twice: once with the first 2 and once with the second. The standard fix has two parts:

1. Sort the input, so equal values sit next to each other.
2. At each level of the tree, skip a value if it equals the previous value tried at that same level: if (i > start && nums[i] == nums[i - 1]) continue;

This allows a 2 to be followed by another 2 deeper in the tree (giving [2, 2]), but never starts two sibling branches with the same value. Subsets II, Combination Sum II and Permutations II all use this idea.

Backtracking is usually exponential, because the number of solutions itself is exponential. A useful estimate is number of nodes in the tree × work per node:

That is why these problems have small limits, such as n <= 10 or n <= 20. If a problem only asks for a count or a best value, and the same sub-problem is reached many times, dynamic programming is usually the better tool; Palindrome Partitioning II is an example.