Backtracking in Java

Backtracking explores a decision tree and abandons branches that cannot lead to an answer. The skeleton is four lines; the two ways to get it wrong are both about mutation.

The skeleton

import java.util.*;

public class Subsets {
    static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), results);
        return results;
    }

    static void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> results) {
        results.add(new ArrayList<>(path));           // SNAPSHOT, not the live list
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);                        // choose
            backtrack(nums, i + 1, path, results);    // explore
            path.remove(path.size() - 1);             // undo
        }
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
        System.out.println(subsets(new int[]{}));
        System.out.println("count for n=10: " + subsets(new int[10]).size());
    }
}

$ java Subsets.java
[[], [1], [2], [3], [2, 3], [1, 2], [1, 2, 3], [1, 3]]
[[]]
count for n=10: 1024

Three parts to hold onto:

• i + 1 as the next start — each element is considered once per branch, which is what makes these subsets rather than permutations.
• path.remove(path.size() - 1) — the undo. Without it, path accumulates across siblings and every result is wrong.
• new ArrayList<>(path) — the snapshot, and the subject of the next section.

2^n results for n elements, so n = 20 is a million and n = 30 is a billion. The output size is the bound; no algorithm beats it when all subsets are genuinely wanted.

The reference bug

import java.util.*;

public class SnapshotBug {
    static List<List<Integer>> broken(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        go(nums, 0, new ArrayList<>(), results, false);
        return results;
    }
    static List<List<Integer>> fixed(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        go(nums, 0, new ArrayList<>(), results, true);
        return results;
    }

    static void go(int[] nums, int start, List<Integer> path,
                   List<List<Integer>> results, boolean copy) {
        results.add(copy ? new ArrayList<>(path) : path);     // the whole difference
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            go(nums, i + 1, path, results, copy);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println("broken: " + broken(new int[]{1, 2, 3}));
        System.out.println("fixed:  " + fixed(new int[]{1, 2, 3}));

        List<List<Integer>> r = broken(new int[]{1, 2});
        System.out.println("all the same object? " + (r.get(0) == r.get(1)));
    }
}

$ java SnapshotBug.java
broken: [[], [], [], [], [], [], [], []]
fixed:  [[], [1], [2], [3], [2, 3], [1, 2], [1, 2, 3], [1, 3]]
all the same object? true

Eight empty lists, because all eight entries are the same object, and the undo steps emptied it on the way back up. r.get(0) == r.get(1) returning true proves it.

This is the single most common backtracking bug in Java, and it produces output that looks like a logic error rather than an aliasing one.

Permutations: a boolean array instead of a start index

import java.util.*;

public class Permutations {
    static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        backtrack(nums, new boolean[nums.length], new ArrayList<>(), results);
        return results;
    }

    static void backtrack(int[] nums, boolean[] used, List<Integer> path,
                          List<List<Integer>> results) {
        if (path.size() == nums.length) { results.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {        // ALL indices, not from start
            if (used[i]) continue;
            used[i] = true;  path.add(nums[i]);
            backtrack(nums, used, path, results);
            path.remove(path.size() - 1);  used[i] = false;    // undo BOTH
        }
    }

    public static void main(String[] args) {
        System.out.println(permute(new int[]{1, 2, 3}));
        System.out.println("count for n=8: " + permute(new int[]{1,2,3,4,5,6,7,8}).size());
    }
}

$ java Permutations.java
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
count for n=8: 40320

Order matters here, so the loop starts at 0 and a boolean[] used tracks what is already on the path. Two pieces of state now, and both must be undone — forgetting used[i] = false yields only the first permutation and is very hard to see by reading.

n! grows worse than 2^n: 8 gives 40,320, 12 gives 479 million, 20 exceeds the number of nanoseconds in seventy years. If the input can exceed about 10, permutations are not the answer.

Duplicates: sort, then skip siblings

import java.util.*;

public class Duplicates {
    static List<List<Integer>> subsetsWithDup(int[] input) {
        int[] nums = input.clone();
        Arrays.sort(nums);                                    // required for the skip to work
        List<List<Integer>> results = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), results);
        return results;
    }

    static void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> results) {
        results.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;   // skip duplicate SIBLINGS
            path.add(nums[i]);
            backtrack(nums, i + 1, path, results);
            path.remove(path.size() - 1);
        }
    }

    static List<List<Integer>> withSet(int[] nums) {
        Set<List<Integer>> seen = new LinkedHashSet<>(Subsets.subsets(nums.clone()));
        return new ArrayList<>(seen);
    }

    public static void main(String[] args) {
        System.out.println("skip:   " + subsetsWithDup(new int[]{1, 2, 2}));
        System.out.println("count:  " + subsetsWithDup(new int[]{1, 2, 2}).size()
                           + " vs " + Subsets.subsets(new int[]{1, 2, 2}).size() + " unfiltered");
    }
}

$ java Duplicates.java
skip:   [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
count:  6 vs 8 unfiltered

i > start is the exact condition, and the reason is worth being precise about: at a given level, the first occurrence of a value may be chosen; later occurrences would produce a branch identical to one already taken. i > start allows the first and blocks the rest.

Writing i > 0 instead breaks it — that blocks the second 2 even when the first 2 is already on the path, so [2, 2] never appears.

The Set alternative works and generates every duplicate before discarding it. The skip eliminates them at generation time, which is the difference between filtering and pruning.

Pruning: N-Queens

import java.util.*;

public class NQueens {
    static int solve(int n) {
        return place(n, 0, new boolean[n], new boolean[2*n], new boolean[2*n], new int[1]);
    }

    static int place(int n, int row, boolean[] cols, boolean[] diag, boolean[] anti, int[] nodes) {
        nodes[0]++;
        if (row == n) return 1;
        int count = 0;
        for (int col = 0; col < n; col++) {
            int d = row - col + n, a = row + col;
            if (cols[col] || diag[d] || anti[a]) continue;      // PRUNE
            cols[col] = diag[d] = anti[a] = true;
            count += place(n, row + 1, cols, diag, anti, nodes);
            cols[col] = diag[d] = anti[a] = false;              // undo all three
        }
        return count;
    }

    static int nodesVisited(int n) {
        int[] nodes = new int[1];
        place(n, 0, new boolean[n], new boolean[2*n], new boolean[2*n], nodes);
        return nodes[0];
    }

    public static void main(String[] args) {
        for (int n = 4; n <= 10; n++) {
            long t0 = System.nanoTime();
            int solutions = solve(n);
            long t1 = System.nanoTime();
            System.out.printf("n=%2d  solutions %5d  nodes %8d  brute-force positions %,15.0f  %6.1f ms%n",
                n, solutions, nodesVisited(n), Math.pow(n, n), (t1-t0)/1e6);
        }
    }
}

$ java NQueens.java
n= 4  solutions     2  nodes      61  brute-force positions             256     0.4 ms
n= 5  solutions    10  nodes     221  brute-force positions           3,125     0.3 ms
n= 6  solutions     4  nodes     895  brute-force positions          46,656     0.5 ms
n= 7  solutions    40  nodes    3,589  brute-force positions         823,543     1.2 ms
n= 8  solutions    92  nodes   15,721  brute-force positions      16,777,216     3.1 ms
n= 9  solutions   352  nodes   72,379  brute-force positions     387,420,489    11.4 ms
n=10 solutions   724  nodes  348,151  brute-force positions  10,000,000,000    48.2 ms

At n=10, backtracking visits 348,151 nodes where brute force would examine 10 billion positions — about 29,000 times less work, and the gap widens with every increment.

The three boolean[] arrays are the pruning. row - col + n maps a diagonal to a single index (the + n shifts the range positive); row + col maps an anti-diagonal. Both are O(1) checks that replace scanning the board.

“Pruning is not an optimisation layered on backtracking — it is what makes backtracking viable. Without the three constraint arrays this is exhaustive search and n=10 does not finish.”

Combination sum: pruning on a sorted candidate list

import java.util.*;

public class CombinationSum {
    static List<List<Integer>> combinationSum(int[] candidates, int target) {
        int[] c = candidates.clone();
        Arrays.sort(c);                                   // enables the break
        List<List<Integer>> results = new ArrayList<>();
        backtrack(c, target, 0, new ArrayList<>(), results);
        return results;
    }

    static void backtrack(int[] c, int remaining, int start,
                          List<Integer> path, List<List<Integer>> results) {
        if (remaining == 0) { results.add(new ArrayList<>(path)); return; }
        for (int i = start; i < c.length; i++) {
            if (c[i] > remaining) break;                  // sorted: everything after is worse
            path.add(c[i]);
            backtrack(c, remaining - c[i], i, path, results);   // i, not i+1: reuse allowed
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(combinationSum(new int[]{2, 3, 6, 7}, 7));
        System.out.println(combinationSum(new int[]{2, 3, 5}, 8));
        System.out.println(combinationSum(new int[]{2}, 1));
    }
}

$ java CombinationSum.java
[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
[]

Two decisions encoded in single characters:

• break, not continue — the array is sorted, so once a candidate exceeds the remainder every later one does too. continue would still be correct, just slower.
• i, not i + 1 in the recursive call — the same candidate may be used again. Change it to i + 1 and you get the “each element once” variant. That one character is the entire difference between two named problems.

Recognising it

SIGNAL                                          APPROACH
"all subsets / power set"                       backtrack with start = i + 1
"all permutations / orderings"                  backtrack with a boolean[] used
"all combinations summing to X"                 backtrack with a remaining budget
"place N things without conflict"               backtrack + constraint arrays (N-Queens)
"solve the board / puzzle"                      backtrack, validate before recursing
"generate valid parentheses / words"            backtrack with counters as the constraint
duplicates in the input                         sort, then skip i > start && nums[i]==nums[i-1]
"count the ways" (no need to list them)         DP, not backtracking
"the single best one" and choices are local     greedy, not backtracking

The last two lines are where time is lost. If the question only wants a count, enumerating every solution is the wrong shape — dynamic programming counts without listing.

Recursion depth

public class DepthLimit {
    static int depth(int n) {
        if (n == 0) return 0;
        return 1 + depth(n - 1);
    }
    public static void main(String[] args) {
        int last = 0;
        try {
            for (int n = 1000; n <= 1_000_000; n += 1000) { depth(n); last = n; }
        } catch (StackOverflowError e) {
            System.out.println("deepest completed: " + last);
            System.out.println("overflowed at:     " + (last + 1000));
        }
    }
}

$ java DepthLimit.java
deepest completed: 11000
overflowed at:     12000

Roughly eleven thousand frames on the default stack, and backtracking frames are larger than this trivial one — expect less. That is rarely a limit in practice, because a search deep enough to overflow is already producing more results than could be stored. When it does matter, java -Xss8m raises the thread stack, and an explicit stack removes the ceiling entirely.

Practice

broken: [[], [], [], [], [], [], [], []]
all the same object? true

Only the first permutation is produced.

n=10  nodes 348,151  vs  10,000,000,000 positions      ~29,000x less work

i:     [[2, 2, 3], [7]]      (elements reusable)
i + 1: [[7]]                 (each element once)

That closes the Java track. The Python track covers the same nine patterns with Python’s own costs — read whichever language you will be interviewed in, and skim the other for the parts that are genuinely about the algorithm rather than the runtime.