Backtracking Pattern in Java - Interview Preparation Guide

Backtracking is DFS over a decision tree with undo steps. It is the default strategy for exhaustive search with constraints.

Core Idea

At each step:

choose
recurse
unchoose (rollback)

Template: Subset-Style Backtracking

What we are doing actually:

Add the current path as one valid partial answer.
Try each next choice.
Recurse deeper.
Roll back before trying the next sibling branch.

public void dfs(int start, int[] nums, List<Integer> path, List<List<Integer>> ans) {
    ans.add(new ArrayList<>(path)); // Snapshot current path before branching further.

    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]); // Choose.
        dfs(i + 1, nums, path, ans); // Explore.
        path.remove(path.size() - 1); // Unchoose.
    }
}

Debug steps:

print path before choose, after choose, and after rollback
verify the copied list goes into ans, not the live path
test with [1,2] so the recursion tree is easy to inspect

Problem 1: Subsets

Problem description: Return all subsets of the given array.

What we are doing actually:

At each index, choose whether to include the current element.
Recurse into the include branch.
Roll back and recurse into the exclude branch.

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

private void backtrack(int idx, int[] nums, List<Integer> path, List<List<Integer>> ans) {
    if (idx == nums.length) {
        ans.add(new ArrayList<>(path)); // One complete subset.
        return;
    }
    path.add(nums[idx]); // Include current value.
    backtrack(idx + 1, nums, path, ans);
    path.remove(path.size() - 1); // Roll back before exclude branch.

    backtrack(idx + 1, nums, path, ans); // Exclude current value.
}

Debug steps:

print idx and path at each recursive entry
verify rollback happens before the exclude branch
compare the recursion tree against the dry run for [1,2]

Dry Run (Subsets of `[1,2]`)

Decision tree:

start []
- include 1 -> [1]
  - include 2 -> [1,2]
  - exclude 2 -> [1]
- exclude 1 -> []
  - include 2 -> [2]
  - exclude 2 -> []

Collected subsets: [], [1], [1,2], [2]

This shows why every level must rollback before exploring sibling branches.

Problem 2: Permutations

Problem description: Return all possible orderings of the given numbers.

What we are doing actually:

Build the permutation one position at a time.
Skip values already used in the current path.
After recursion, unmark the value so another branch can use it.

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    dfs(nums, used, new ArrayList<>(), ans);
    return ans;
}

private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
    if (path.size() == nums.length) {
        ans.add(new ArrayList<>(path)); // One complete ordering.
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true; // Reserve this number for current permutation.
        path.add(nums[i]);
        dfs(nums, used, path, ans);
        path.remove(path.size() - 1); // Roll back path.
        used[i] = false; // Make number available again.
    }
}

Debug steps:

print path and used at each depth
verify every used[i] = true has a matching rollback to false
test [1,2,3] and count that the answer size becomes 6

Problem 3: Combination Sum

Problem description: Find all combinations whose sum equals the target, where each candidate can be reused.

What we are doing actually:

At each index, decide whether to take the current candidate.
If we take it, stay on the same index because reuse is allowed.
If we skip it, move to the next index.
Prune immediately when the remaining sum goes negative.

public List<List<Integer>> combinationSum(int[] c, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(0, target, c, new ArrayList<>(), ans);
    return ans;
}

private void dfs(int i, int remain, int[] c, List<Integer> path, List<List<Integer>> ans) {
    if (remain == 0) {
        ans.add(new ArrayList<>(path)); // Found one valid combination.
        return;
    }
    if (remain < 0 || i == c.length) return;

    path.add(c[i]); // Take current candidate.
    dfs(i, remain - c[i], c, path, ans); // Stay on same index because reuse is allowed.
    path.remove(path.size() - 1); // Roll back take branch.

    dfs(i + 1, remain, c, path, ans); // Skip current candidate.
}