Lesson 13.1 · Backtracking

Choose, Explore, Unchoose

Every backtracking function adds a choice to the current path, recurses, then removes it. Draw the decision tree first.

15 min

Think of it like this

Choosing an outfit by trying things on: put on a shirt, try trousers with it, take the trousers off, try the next pair. When every pair has been tried with that shirt, take the shirt off and try the next shirt. Every combination is tried, and you never wear two shirts at once.

1.The decision tree

For subsets of [1, 2, 3], each element is a yes/no decision, giving a tree with 2³ = 8 leaves. Backtracking walks this tree depth-first with one shared path list: going down adds an element, coming back up removes it.

The shared path is why the "unchoose" step matters: without it, choices from one branch leak into the next.

▶ Dry run: Building subsets of [1, 2, 3]nums = [1, 2, 3]

path(list)

empty

results(list)

[]

Step 1/5Record the empty path, then try adding each remaining element in turn.

2.The template

Copy the path when recording it (new ArrayList<>(path)); otherwise every result points to the same list, which ends up empty.

Subsets.java

import java.util.*;

public class Main {
    static void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {
        out.add(new ArrayList<>(path));              // record a copy
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);                       // choose
            backtrack(nums, i + 1, path, out);       // explore
            path.remove(path.size() - 1);            // unchoose
        }
    }
    public static void main(String[] args) {
        List<List<Integer>> out = new ArrayList<>();
        backtrack(new int[]{1, 2, 3}, 0, new ArrayList<>(), out);
        System.out.println(out);
    }
}

Output

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Remember

Choose → explore → unchoose.
Record copies of the path.
Draw the decision tree before coding.

Common mistakes

Adding path itself to results (all entries end up identical).
Forgetting to remove the last choice.

Words used in this lesson

Decision tree: A tree where each level is one choice and each path from the root is a partial answer.
Path: The choices made so far on the way down the tree.
Pruning: Stopping a branch early because it can't lead to a valid answer.

Command Palette

Choose, Explore, Unchoose

1.The decision tree

2.The template