Backtracking method

Many problems ask for every solution, or for one that satisfies rules: all subsets, all arrangements, a placement that violates no constraint. Such a problem can be drawn as a **decision tree**. The root is the empty solution. Each level is one decision (include this value or not, which letter comes next, which column holds this queen) and each edge is one possible answer to it. A leaf, or any node that satisfies the goal, is a solution.

Backtracking is a depth-first walk over that tree. The tree is never stored: it exists implicitly in the recursion, and the call stack holds the path from the root to the current node. Run the animation to watch the tree for the three subsets of {1, 2, 3} grow: every node is a subset, and the 8 nodes are the 8 subsets.

1static void subsets(int[] a, int start, List<Integer> path, List<List<Integer>> out) {
2    out.add(new ArrayList<>(path));                          // every partial solution is a subset
3    for (int i = start; i < a.length; i++) {
4        path.add(a[i]);                                      // choose
5        subsets(a, i + 1, path, out);                        // explore
6        path.remove(path.size() - 1);                        // unchoose
7    }
8}

Every backtracking routine has the same three-beat rhythm inside its loop: **choose** one option (add it to the partial solution), **explore** everything that can follow it (a recursive call), and **unchoose** it (remove it again), so the next option starts from exactly the state the loop started with. The two Java rules that make it work: add a copy of the path to the results, and undo with the exact inverse of the choice.

Step through the “Three values” preset and watch the message log: “Choose 2”, the deeper calls, then “Unchoose 2: back to [1]”. The partial solution in the first auxiliary row always returns to its earlier value after the unchoose.

1interface Search<O> {
2    boolean complete();                                       // is the partial solution a full answer?
3    List<O> options();                                        // the choices available right now
4    void apply(O option);                                     // choose
5    void undo(O option);                                      // unchoose: the exact inverse of apply
6    String snapshot();                                        // a copy of the current partial solution
7}
8static <O> void solve(Search<O> s, List<String> out) {
9    if (s.complete()) { out.add(s.snapshot()); return; }
10    for (O o : s.options()) {
11        s.apply(o);                                           // choose
12        solve(s, out);                                        // explore
13        s.undo(o);                                            // unchoose: restore the state exactly
14    }
15}

1static void subsets(int[] a, int start, List<Integer> path, List<List<Integer>> out) {
2    out.add(new ArrayList<>(path));                          // every partial solution is a subset
3    for (int i = start; i < a.length; i++) {
4        path.add(a[i]);                                      // choose
5        subsets(a, i + 1, path, out);                        // explore
6        path.remove(path.size() - 1);                        // unchoose
7    }
8}

The **partial solution** is the decisions made on the way from the root to the current node. It can be a list (the chosen values so far), a set of occupied squares, or an assignment of colours to the first few vertices. It is the state that choose and unchoose modify, and it is what a solution is copied from when the search reaches a complete answer.

Keep the partial solution *small* and *incrementally updatable*. Alongside it, keep whatever lets you test a new option in O(1): a boolean[] used, a column/diagonal marker array for queens, running sums. The animation's first auxiliary row shows the partial solution at every step; the final result lists every complete solution that was copied out of it.

1static List<List<Integer>> combinations(int[] a, int k) {
2    List<List<Integer>> out = new ArrayList<>();
3    build(a, k, 0, new ArrayList<>(), out);
4    return out;
5}
6private static void build(int[] a, int k, int start, List<Integer> path, List<List<Integer>> out) {
7    if (path.size() == k) { out.add(new ArrayList<>(path)); return; }     // copy the partial solution
8    for (int i = start; i < a.length; i++) {
9        path.add(a[i]);                                                   // choose
10        build(a, k, i + 1, path, out);                                    // explore
11        path.remove(path.size() - 1);                                     // unchoose
12    }
13}

Unchoose must reverse *everything* the choice changed. The bug that hides longest is a change that is not undone: a used[i] = true without the matching used[i] = false, a counter incremented but never decremented, a cell marked visited and never freed. The search then silently skips valid branches, so it finds fewer solutions than exist, with no exception to warn you.

Two patterns make undoing safe. **Mutate and restore**: change the shared state, recurse, change it back (as permute does with used[]). **Pass copies**: give each recursive call its own new value (String s + c, an immutable list), so there is nothing to undo, at the cost of allocating. The permutation animation shows the mutate-and-restore pattern: look at which indices are marked used on the way down and freed on the way back.

1static void permute(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> out) {
2    if (path.size() == a.length) { out.add(new ArrayList<>(path)); return; }
3    for (int i = 0; i < a.length; i++) {
4        if (used[i]) continue;                                // already on the path
5        used[i] = true; path.add(a[i]);                       // choose: two pieces of state change
6        permute(a, used, path, out);
7        path.remove(path.size() - 1); used[i] = false;        // unchoose: both are restored
8    }
9}

1static void permute(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> out, boolean unique) {   // sort a first when unique
2    if (path.size() == a.length) { out.add(new ArrayList<>(path)); return; }
3    for (int i = 0; i < a.length; i++) {
4        if (used[i]) continue;                                            // already on the path
5        if (unique && i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;   // a twin of the previous value, which is free
6        used[i] = true; path.add(a[i]);                                   // choose
7        permute(a, used, path, out, unique);                              // explore
8        path.remove(path.size() - 1); used[i] = false;                    // unchoose
9    }
10}

**Pruning** abandons a branch as soon as it provably cannot lead to a solution, so the whole subtree below it is never visited. The earlier the rule fires, the more it saves. For combinations of size k from n values, a branch that has chosen j values and has only m values left can reach size k only if j + m ≥ k; otherwise stop.

Run the “Pruning on” and “Pruning off (same answers, more work)” presets: both list the same 10 combinations, but with pruning the tree has 24 nodes instead of 26. The saving grows quickly with the size of the input: pruning never changes the answers, only the work. A correct prune must be *safe*: it may only cut branches that contain no solution.

1static void combine(int[] a, int k, int start, List<Integer> path, List<List<Integer>> out, boolean prune) {
2    if (path.size() == k) { out.add(new ArrayList<>(path)); return; }
3    for (int i = start; i < a.length; i++) {
4        if (prune && path.size() + (a.length - i) < k) break;      // too few values left to reach size k
5        path.add(a[i]);                                           // choose
6        combine(a, k, i + 1, path, out, prune);                   // explore
7        path.remove(path.size() - 1);                             // unchoose
8    }
9}

1static void combine(int[] a, int k, int start, List<Integer> path, List<List<Integer>> out, boolean prune) {
2    if (path.size() == k) { out.add(new ArrayList<>(path)); return; }
3    for (int i = start; i < a.length; i++) {
4        if (prune && path.size() + (a.length - i) < k) break;      // too few values left to reach size k
5        path.add(a[i]);                                           // choose
6        combine(a, k, i + 1, path, out, prune);                   // explore
7        path.remove(path.size() - 1);                             // unchoose
8    }
9}

A **validity check** decides whether an option may be added to the partial solution. Put it *before* the choose step, so an invalid option never enters the tree. For parentheses, the rules are: an opening parenthesis is allowed while fewer than n are used; a closing one is allowed only while something is open. With those two checks every string that reaches length 2n is balanced, and no balance test is needed at the end.

In the animation, rejected options appear as ✗ nodes with the reason in the log. For n = 3 the tree has 35 nodes and 5 solutions; without the checks the tree would contain all 2^6 = 64 strings of six parentheses at its leaves.

1static void gen(int open, int close, int n, StringBuilder sb, List<String> out) {
2    if (sb.length() == 2 * n) { out.add(sb.toString()); return; }
3    if (open < n) {                                            // an opening parenthesis is still available
4        sb.append('(');
5        gen(open + 1, close, n, sb, out);
6        sb.deleteCharAt(sb.length() - 1);
7    }
8    if (close < open) {                                        // a closing one is valid only if something is open
9        sb.append(')');
10        gen(open, close + 1, n, sb, out);
11        sb.deleteCharAt(sb.length() - 1);
12    }
13}

1static void gen(int open, int close, int n, StringBuilder sb, List<String> out) {
2    if (sb.length() == 2 * n) { out.add(sb.toString()); return; }
3    if (open < n) {                                            // an opening parenthesis is still available
4        sb.append('(');                                        // choose
5        gen(open + 1, close, n, sb, out);                      // explore
6        sb.deleteCharAt(sb.length() - 1);                      // unchoose
7    }
8    if (close < open) {                                        // a closing one is valid only if something is open
9        sb.append(')');
10        gen(open, close + 1, n, sb, out);
11        sb.deleteCharAt(sb.length() - 1);
12    }
13}