The 3 Backtracking Patterns Behind Most Interview Questions

Backtracking builds answers one choice at a time, explores where each choice leads, and undoes it before trying the next one.

Almost every backtracking question is a twist on one of these three patterns. Learn their decision trees and you can adapt them quickly.

1) Subsets

Generate every subset of a list. Each path from the root of the decision tree is a subset, so every node, not just the leaves, is part of the answer. Only choosing elements after the current index stops the same subset from appearing twice.

def subsets(nums):
    out = []
    def build(start, path):
        out.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            build(i + 1, path)
            path.pop()
    build(0, [])
    return out

2) Combinations

Choose exactly k items out of n. The tree looks like the subsets tree, but you stop going deeper once the path holds k items, and only those full paths are answers.

def combine(n, k):
    out = []
    def build(start, path):
        if len(path) == k:
            out.append(path[:])
            return
        for x in range(start, n + 1):
            path.append(x)
            build(x + 1, path)
            path.pop()
    build(1, [])
    return out

3) Permutations

Produce every ordering of a list. Unlike subsets, order matters, so each level may pick any number not used yet. Only the leaves, where every number has been placed, are answers.

def permute(nums):
    out = []
    def build(path, used):
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i, x in enumerate(nums):
            if not used[i]:
                used[i] = True
                build(path + [x], used)
                used[i] = False
    build([], [False] * len(nums))
    return out