Pattern 18 of 27

Backtracking Basics

Build every candidate one choice at a time, recurse, then undo the choice so the same working list serves every branch.

Cost: O(n · 2^n) for subsets, O(n · n!) for permutations
Problems: 6

When to reach for it

The prompt asks for all permutations, combinations, or subsets.
The output itself is exponential in size, so no polynomial shortcut exists.
Each step picks one of the remaining options.

How it works

Backtracking is a DFS over a tree of decisions. At each level you pick one option, recurse to decide everything after it, then undo the pick before trying the next option. Subsets record every node of that tree, combinations record the nodes at one fixed depth, and permutations track used numbers instead of a start index. Duplicate inputs are handled by sorting first and skipping a value equal to the one just tried at the same level.

The template

Written for Subsets (write-up)

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

    def choose(start):
        out.append(path[:])           # every partial path is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])      # choose
            choose(i + 1)             # explore
            path.pop()                # un-choose

    choose(0)
    return out

Open in the editor Trace it line by line

Six problems, in learning order

1.PermutationsLeetCode 46A used array, since any position can take any unused number.Medium
2.Permutations IILeetCode 47Sort, then skip a number equal to the previous one while the previous one is unused.Medium
3.CombinationsLeetCode 77Subsets of a fixed size k; prune when too few numbers remain.Not in the curated 370 yet.Medium
4.SubsetsLeetCode 78Record every partial path as a subset.Medium
5.Subsets IILeetCode 90Sort and skip equal neighbours at the same depth.Medium
6.Combination SumLeetCode 39Recurse with the same start index, because a number may be reused.Medium

What usually goes wrong

Appending the working path instead of a copy of it, so every result ends up as the same empty list.
Forgetting to undo the choice after the recursive call returns.
Skipping duplicates across levels instead of only within the same level.