Backtracking

The backtracking coding pattern for interviews. Choose, explore, undo, with a step-through of subsets as a decision tree, pruning and duplicate handling, code in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Mid-level14 min read

Read first: Tree traversal

Some problems ask for every answer: all subsets, all permutations, every way to place eight queens, every combination that sums to a target. There’s no clever shortcut, because the output itself is huge. What you control is doing the search cleanly, never building the same answer twice, and abandoning a branch the moment it can’t lead anywhere.

Backtracking is that search. Picture the choices as a tree: the root is “nothing chosen yet”, and each edge is one choice. A depth-first walk of that tree, using one shared list for the current path, visits every answer. The whole pattern is three lines: choose, explore, undo.

How to spot it

“All”, “every”, “generate”, “list all possible”: subsets, permutations, combinations, partitions, placements.
Constraint puzzles: N-queens, sudoku, word search in a grid.
Small inputs. Constraints like n ≤ 10 or n ≤ 20 are a strong hint that an exponential search is expected.

Sometimes the problem asks how many ways, or the best way, instead of listing them. Then it’s often dynamic programming. Counting doesn’t need to build each answer, and the subproblems usually overlap.

Watch it run

Subsets of [1, 2, 3], drawn as the tree of choices. Each node is the path at that moment, and every node is a subset. Follow the path box: it grows on the way down and shrinks on the way back, and it’s the same list the whole time.

path

empty

result

∅11,21,2,31,322,33

def backtrack(start, path):
result.append(path[:]) # a subset
for j in range(start, len(nums)):
path.append(nums[j]) # choose
backtrack(j + 1, path) # explore
path.pop() # undo

Start with the empty path. It is a subset too.

1 / 15

Notice which branches don’t exist: there’s no {2, 1}, because after choosing 2, the loop only looks at numbers after it. That start index is what makes each subset appear exactly once, in increasing order.

The template

Subsets, permutations and combination sum. They differ in only two places: where the loop starts, and when a path counts as an answer.

Backtracking.javaexample.pyBacktracking.csmain.goexample.ts

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

    // Choose, explore, undo. One shared path; every call records it, then tries each later
    // number. start keeps each subset in one order, so [1, 2] is built but [2, 1] never is.
    static void subsets(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path)); // a copy: path keeps changing after this
        for (int j = start; j < nums.length; j++) {
            path.add(nums[j]); // choose
            subsets(nums, j + 1, path, result); // explore
            path.remove(path.size() - 1); // undo, so the next branch starts from the same path
        }
    }

    static List<List<Integer>> permutations(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        permute(nums, new boolean[nums.length], new ArrayList<>(), result);
        return result;
    }

    // Order matters now, so every position may take any unused number. used[] replaces start.
    static void permute(
            int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int j = 0; j < nums.length; j++) {
            if (used[j]) continue;
            used[j] = true;
            path.add(nums[j]);
            permute(nums, used, path, result);
            path.remove(path.size() - 1);
            used[j] = false;
        }
    }

    static List<List<Integer>> combinationSum(int[] candidates, int target) {
        int[] sortedCandidates = candidates.clone();
        Arrays.sort(sortedCandidates);
        List<List<Integer>> result = new ArrayList<>();
        combine(sortedCandidates, 0, target, new ArrayList<>(), result);
        return result;
    }

    // Numbers may repeat, so recurse with j, not j + 1. Sorting first lets us prune: once a
    // candidate is bigger than what's left, every candidate after it is too, so break.
    static void combine(int[] sortedCandidates, int start, int remaining, List<Integer> path,
            List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int j = start; j < sortedCandidates.length && sortedCandidates[j] <= remaining; j++) {
            path.add(sortedCandidates[j]);
            combine(sortedCandidates, j, remaining - sortedCandidates[j], path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        check(subsets(new int[] {1, 2, 3}).equals(List.of(List.of(), List.of(1), List.of(1, 2),
                List.of(1, 2, 3), List.of(1, 3), List.of(2), List.of(2, 3), List.of(3))));
        check(permutations(new int[] {1, 2, 3}).size() == 6);
        check(permutations(new int[] {1, 2}).get(1).equals(List.of(2, 1)));
        check(combinationSum(new int[] {2, 3, 6, 7}, 7)
                .equals(List.of(List.of(2, 2, 3), List.of(7))));
        System.out.println("ok: subsets, permutations and combinationSum");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

Problem	Loop over	Record when	Recurse with
Subsets	`j` from `start`	every call	`j + 1`
Combinations of size k	`j` from `start`	`len(path) == k`	`j + 1`
Combination sum (reuse allowed)	`j` from `start`	`remaining == 0`	`j`
Permutations	every unused `j`	`len(path) == len(nums)`	mark `used[j]`

Skipping duplicates

When the input has repeats, like [1, 2, 2], the plain template builds [1, 2] twice, once with each 2. Sort the input, then in the loop skip an element equal to the one before it at the same depth: if j > start and nums[j] == nums[j - 1]: continue. The j > start part matters. It still allows [2, 2], where the second 2 is chosen one level deeper, but stops a second 2 being tried as the same choice twice.

Pruning

Pruning is what makes backtracking fast enough. In combination sum, sort the candidates. Once one is bigger than what’s left, every later one is too. So break out of the loop, instead of trying them. In N-queens, keep sets of used columns and diagonals (row - column and row + column). Then each placement is checked in O(1), and impossible rows are dropped at once.

Grids: word search

The choices are the four neighbors, and the path is the cells used so far. Mark a cell when you step on it (for example, change it to #), and restore it when you return. That restore is the “undo”, and forgetting it is the most common bug: later searches then think the cell is still in use.

Complexity

Backtracking is exponential because the answers are. Subsets of n items: 2ⁿ answers, each up to n long, so O(n × 2ⁿ). Permutations: n! answers, O(n × n!). State the output size and say the search can’t do better than writing out every answer. Memory beyond the output is O(n): one path and a recursion n deep.

Say this out loud

There are 2ⁿ subsets, so any solution is at least O(2ⁿ). I’ll do a depth-first search over the choices with one shared path: add an element, recurse on the later ones, then remove it.

Interview questions

Interviewer asksWhy loop from start instead of from 0 in subsets?

A subset is a set, so {1, 2} and {2, 1} are the same answer. Only allowing elements after the last one chosen means every subset is built in exactly one order, increasing by index, so each appears once. Permutations want every order, so they loop from 0 and skip used elements instead.

Interviewer asksCan you generate subsets without recursion?

Yes, two ways. Iteratively: start with [[]], and for each number, add a copy of every existing subset with that number appended. Or with bits: for each mask from 0 to 2ⁿ - 1, the subset contains element i when bit i is set. Both are O(n × 2ⁿ). The recursive version is still the one to know, because it extends to pruning and constraints and the others don’t.

Interviewer asksN-queens: how do you check a placement in O(1)?

Place one queen per row, so rows never clash. Keep three sets: used columns, used row - column diagonals and used row + column anti-diagonals. Every square on the same diagonal shares the same row - column, and every square on the same anti-diagonal shares row + column. A square is safe when its column and both diagonal values are unused. Add them when placing, remove them when undoing.

Practice

10 problems on LeetCode: 9 medium, 1 hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

Use it when the problem asks for all solutions, or a constraint puzzle has small inputs.
The shape: choose, explore, undo, with one shared path.
Use a start index for sets, and a used array for orderings. Recurse with j when items can repeat.
Duplicates: sort, then skip equal elements at the same depth (j > start).
Cost: exponential, matching the output size. Prune early to cut whole branches.