Coding Interview Patterns

Backtracking Templates

A single reusable shape — choose, recurse, un-choose — generates every permutation, subset, and constraint-satisfying configuration (N-Queens, Sudoku) with only the loop bounds and validity check changing between problems.

The three-step skeleton: choose an option, recurse on the reduced problem, undo the choice before trying the next option
Subsets: at each element, branch into "include it" and "exclude it"
Permutations: track a used[] array (or swap elements in place) so each element appears exactly once per path
Constraint problems (N-Queens, Sudoku): check partial validity before recursing deeper — this pruning is what keeps exponential search spaces tractable in practice
The "undo" step is what makes it backtracking rather than plain recursive brute force — it lets the same mutable state be reused across all branches instead of copying it

Generic template applied to subsets

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

static void backtrack(int[] nums, int start, Deque<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));         // every path is a valid subset — record it
    for (int i = start; i < nums.length; i++) {
        path.addLast(nums[i]);                  // choose
        backtrack(nums, i + 1, path, result);    // recurse
        path.removeLast();                       // un-choose
    }
}

When backtracking is (and isn't) the right tool
Situation	Approach
Need every valid configuration, search space is small/prunable	backtracking
Need only the count or optimum, overlapping subproblems exist	Dynamic Programming instead — memoize rather than enumerate
No constraints to prune with, pure enumeration	plain recursion or iteration, backtracking adds no value