Backtracking

Written Explanation

The pattern

A backtracking method has a current answer (a list built so far) and repeats this loop of decisions:

1. Choose: add one option to the current answer.
2. Explore: call the method recursively to complete the answer from there.
3. Un-choose: remove the option you added, so the current answer is exactly as it was before.

The base case is "the answer is complete": save it and return. Because step 3 restores the state, the next choice starts from a clean slate. Un-choosing on the way back up the call stack is where the name "backtracking" comes from.

Subsets: take it or skip it

A subset of {1, 2, 3} keeps some items and drops the others, in any combination. For each item there are two decisions: skip or take. With n items, that is 2 × 2 × ... × 2 = 2ⁿ subsets (the empty subset and the full set both count).

static void subsets(int[] a, int i, List<Integer> cur, List<List<Integer>> out) {
    if (i == a.length) {                       // base case: decided about every item
        out.add(new ArrayList<>(cur));         // save a COPY
        return;
    }
    subsets(a, i + 1, cur, out);               // skip a[i]
    cur.add(a[i]);                             // choose: take a[i]
    subsets(a, i + 1, cur, out);               // explore
    cur.remove(cur.size() - 1);                // un-choose
}

Here i is the item we are deciding about; cur is the subset so far. On {1, 2, 3} my run printed:

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

Eight subsets, 2³. The order looks odd because we try "skip" first and recursion goes deepest first; the set of results is what matters.

cur.remove(cur.size() - 1) removes the last item by index. For a List<Integer>, careful: remove(int index) removes by position, while remove(Object o) removes a value. Passing an int expression, as here, picks the position version. The List documentation describes remove(int) as removing the element at the given position.

Why copy the list?

out.add(cur) stores a reference to the same list that keeps changing. After the search finishes, cur has been un-chosen back to empty, so every saved entry shows the same empty list. To confirm, I ran a version with out.add(cur) on {1, 2} and printed:

[[], [], [], []]

Four entries (correct count), all empty (wrong contents). The fix is new ArrayList<>(cur), which makes an independent snapshot at that moment.

Permutations: every ordering

A permutation is an ordering of all the items. For n items there are n × (n-1) × ... × 1 = n! of them: n choices for the first position, n-1 for the second, and so on. Now each step is a loop over the items not yet used, so we keep a boolean[] used to mark what is already in cur.

static void perms(int[] a, boolean[] used, List<Integer> cur, List<List<Integer>> out) {
    if (cur.size() == a.length) { out.add(new ArrayList<>(cur)); return; }
    for (int i = 0; i < a.length; i++) {
        if (used[i]) continue;                 // already in the answer
        used[i] = true; cur.add(a[i]);         // choose
        perms(a, used, cur, out);              // explore
        cur.remove(cur.size() - 1);            // un-choose
        used[i] = false;
    }
}

For {1, 2, 3} my run printed:

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

Six results, 3! = 6. Notice that un-choose now restores two things: the list and the used flag. Every piece of state you change when choosing must be undone.

Growth: 2ⁿ and n!

For n = 4 my run gave 16 subsets and 24 permutations. The 10 and 20 rows are arithmetic. Generating all of something with 20 items as permutations is impossible in practice. Backtracking is for small inputs, or for problems where pruning cuts most of the search away.

Pruning: stop dead ends early

Problem: find every group of numbers from {1, 2, 3, 4, 5, 6}, each used at most once, that adds up to 7.

A plain search tries all subsets. But if the numbers are sorted and positive, as soon as the next number is larger than the amount still needed, no later number can work either, so we can stop that loop.

static void combos(int[] a, int start, int remaining, List<Integer> cur,
                   List<List<Integer>> out) {
    if (remaining == 0) { out.add(new ArrayList<>(cur)); return; }
    for (int i = start; i < a.length; i++) {
        if (a[i] > remaining) break;           // prune: a is sorted and positive
        cur.add(a[i]);                         // choose
        combos(a, i + 1, remaining - a[i], cur, out);   // explore
        cur.remove(cur.size() - 1);            // un-choose
    }
}

start makes sure we only look at items after the one we just took, so the same group is not produced in two orders. The pruning relies on two assumptions (sorted, positive); with negative numbers it would be wrong.