Backtracking

Choose, recurse, undo

Backtracking is depth-first search over decisions rather than over a graph. You make a choice, explore everything that follows from it, then reverse the choice and try the next one.

Every backtracking method has the same three parts:

The undo is what makes it correct. Without it, choices leak from one branch into the next.

Generating subsets

static List<Integer> current = new ArrayList<>();
static List<List<Integer>> results = new ArrayList<>();

static void subsets(int[] values, int index) {
    if (index == values.length) {
        results.add(new ArrayList<>(current));   // copy, not the live list
        return;
    }

    // choice 1: skip this element
    subsets(values, index + 1);

    // choice 2: take it
    current.add(values[index]);
    subsets(values, index + 1);
    current.remove(current.size() - 1);          // undo
}

Permutations

Here the state to undo is two things — the list and the used-markers.

static void permute(int[] values, boolean[] used) {
    if (current.size() == values.length) {
        results.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < values.length; i++) {
        if (used[i]) continue;

        used[i] = true;                  // choose
        current.add(values[i]);

        permute(values, used);           // recurse

        current.remove(current.size() - 1);
        used[i] = false;                 // undo both
    }
}

Both mutations must be reversed. Undoing only one leaves the search in a corrupt state that is hard to diagnose.

Permutations grow as n factorial — 10 items is about 3.6 million arrangements, 13 is over 6 billion. Check the size before choosing this approach.

Choosing k of n

Passing a start index keeps combinations in increasing order, so each is produced once rather than in every possible ordering:

static void choose(int[] values, int start, int k) {
    if (current.size() == k) {
        results.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < values.length; i++) {
        current.add(values[i]);
        choose(values, i + 1, k);        // i + 1, not start + 1
        current.remove(current.size() - 1);
    }
}

Passing i + 1 rather than start + 1 is the detail. It advances past the element just used, which is what prevents duplicates.

Pruning

The search space grows exponentially, so abandoning hopeless branches early is often what makes a solution feasible.

static boolean canReachTarget(int[] values, int index, int sum, int target) {
    if (sum == target) return true;
    if (sum > target) return false;                  // prune: already too big
    if (index == values.length) return false;

    // take it, or skip it
    return canReachTarget(values, index + 1, sum + values[index], target)
        || canReachTarget(values, index + 1, sum, target);
}

The sum > target check cuts off entire subtrees. Assuming all values are positive, adding more can never bring an overshooting sum back down, so nothing below that branch can succeed.

Carrying sum as a parameter rather than recomputing it at the base case is what makes the prune possible at all — you need the running value at every level, not just the end.

A worked example: placing rooks

Place n rooks on an n × n board so none share a row or column.

static int countArrangements(int n, int row, boolean[] usedColumns) {
    if (row == n) return 1;              // placed them all

    int total = 0;
    for (int col = 0; col < n; col++) {
        if (usedColumns[col]) continue;

        usedColumns[col] = true;         // choose
        total += countArrangements(n, row + 1, usedColumns);
        usedColumns[col] = false;        // undo
    }
    return total;
}

Handling one row per call means rows can never clash, so only columns need tracking. Choosing the right thing to iterate over frequently removes half the constraints.

Recognising a backtracking problem

Next

Related