Pattern8 min read

Backtracking

DFS through the decision tree, pruning branches that cannot lead to a solution.

backtrackingrecursion

Intro

Backtracking is a disciplined depth-first search through the space of partial solutions. You make a choice, recurse, then 'unmake' the choice before trying the next one. Pruning — stopping a branch early when it cannot satisfy the constraint — is what stops the exponential blow-up.

Key insight

Choose → Explore → Unchoose. The undo step is what makes the search bounded by the answer's size, not the tree's size.

Approach

1Pick a state representation: the current path + remaining choices.
2If state is a complete answer, record it.
3Else, for each candidate choice that keeps state valid: apply, recurse, undo.
4Prune aggressively: any deductive 'this can't work' shortcut.

Complexity

Time

O(branching^depth) — usually exponential; pruning is what saves you

Space

O(depth) for the recursion stack + O(answer size)

Code

LC 78 — all subsetsjava

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), ans);
    return ans;
}
void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
    ans.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, ans);
        path.remove(path.size() - 1);
    }
}

Pitfalls

Adding the partial path to the answer by reference — you'll later mutate it.
Forgetting the 'unchoose' step.
Skipping pruning — turns an O(2ⁿ) into a TLE.

Variants & follow-ups

Permutations (LC 46)
N-Queens (LC 51)
Combination Sum (LC 39)