Backtracking Pattern: Template + 105 LeetCode Problems

What the backtracking pattern is

Backtracking is depth-first search over the tree of partial solutions, with one discipline attached: every choice made on the way down is undone on the way back up, so a single mutable path can stand in for the whole tree instead of copying state at every node. The template is always the same three lines — choose, recurse, un-choose — and the two decisions that make a problem specific are what the recursion index means and where the pruning goes. Pruning is what separates a working answer from a timing out one: rejecting a branch at depth two skips every leaf beneath it, so a check placed before the recursive call is worth far more than the same check at the leaf. The one thing to be deliberate about is the copy: appending the live path to the result list stores a reference that later mutations will corrupt, so the copy has to be taken when the answer is recorded.

When to use it

• —The problem asks for all subsets, permutations, combinations, partitions or paths — the arrangements themselves, not a count.
• —A valid answer is built incrementally and partial answers can be judged invalid early.
• —The constraints are small — n around 20 or less — because the search is exponential by nature.
• —You are placing things under conflict rules: queens, sudoku digits, word squares.

The backtracking template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 105 problems listed below.

def subsets(nums):
    result, path = [], []

    def explore(start):
        result.append(path[:])            # copy: path keeps mutating after this
        for i in range(start, len(nums)):
            path.append(nums[i])          # choose
            explore(i + 1)                # explore what is left
            path.pop()                    # un-choose, restoring the caller's state

    explore(0)
    return result

Complexity characteristics

Time

Exponential — O(n·2ⁿ) for subsets, O(n·n!) for permutations

Auxiliary space

O(n), plus the output

The search tree has one leaf per candidate answer, so the running time is the number of answers times the cost of recording each one. There is no polynomial version, which is why the constraints on these problems are small. Pruning does not change the worst case but changes the observed time enormously, because rejecting a branch at depth two removes every leaf beneath it. The working space is the recursion depth and the single mutable path; the result list is output, not working memory.

All 105 backtracking LeetCode problems

Every problem in the library the backtracking pattern applies to, grouped by LeetCode's own difficulty rating. 86 of the 105 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Backtracking pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.