Backtracking Pattern: One Template for Subsets, Permutations, and Combinations

TL;DR: Backtracking is one recursive template: make a choice, explore what follows, then undo the choice so the next branch starts clean. Subsets, combinations, and permutations are not three algorithms, they are that template with a different loop start and a different rule about reuse. Learn the template plus a three-row table and you cover a family that fills entire interview rounds, including Combination Sum, Palindrome Partitioning, Word Search, and N-Queens. The most common reason a first attempt fails is a single missing character, and we will name it precisely.

This is the tenth deep dive in our pattern series (the full map lives in the hub), following prefix sum. Backtracking is where many candidates first meet real recursion, and it produces a distinctive failure mode: the code looks right, runs without error, and returns a list of empty or identical entries. That failure has one cause, it takes one character to fix, and knowing it in advance is worth more than another twenty solved problems.

The tell: how to recognize a backtracking problem

Suspect this pattern when the question asks you to produce every valid arrangement, not to count them or optimize them:

• "return all possible subsets / combinations / permutations"
• "generate every valid string / partition / placement"
• "find all ways to ..."
• "return all valid board configurations" (N-Queens, Sudoku)
• the return type is a list of lists, or a list of strings

The last signal is the most reliable one. If the answer is a collection of items, think backtracking. If the answer is a single number, whether a count or a best value, think dynamic programming or a greedy approach instead. Combination Sum asks for the actual combinations, so it is backtracking. Coin Change asks only for the fewest coins, so it is dynamic programming. Same shaped input, different tool, and interviewers use that pair deliberately.

The one insight the whole pattern rests on

Here is the sentence that is the pattern: the recursion builds a single path, and the un-choose step restores the state so the next branch starts from where this one began.

Picture the search as a tree. Each level decides one position, each branch is one option for it, and a full root-to-leaf walk is one candidate answer. There is only ever one path being built, held in a single list that is pushed to on the way down and popped from on the way back up. That is why the pattern is cheap in memory even when the output is enormous: you store one path plus the results, not the whole tree.

Backtracking is depth-first search over that decision tree, with one addition: before exploring a branch you may check whether it can possibly lead anywhere, and skip it if not. That check is called pruning, and it is what separates a solution that finishes from one that times out on N-Queens.

The template

Every problem in this family is this shape:

def backtrack(path, start):
    if is_complete(path):
        results.append(path[:])          # copy the path, do not append the path
        return
    for choice in available_choices(start):
        if not is_valid(choice, path):
            continue                     # prune
        path.append(choice)              # choose
        backtrack(path, next_start)      # explore
        path.pop()                       # un-choose

path[:] is the character-level detail that decides whether your solution works. path is one list that is mutated throughout the search. Appending it to results stores a reference, so every entry in results points at the same list, and when the recursion finishes and that list has been popped back to empty, every entry reads as empty. Copy it with path[:] (or list(path), or new ArrayList<>(path) in Java) and the problem disappears. If your output is a list of identical or empty entries, this is the cause, every time.

The three variants in one table

The template does not change. Two knobs do:

The start parameter is what prevents permutations of the same choice set from being generated twice. Subsets and combinations treat [1,2] and [2,1] as the same answer, so they only ever look forward. Permutations treat them as different, so the loop restarts at 0 and a used array does the excluding instead.

Subsets:

def subsets(nums):
    results, path = [], []
    def backtrack(start):
        results.append(path[:])          # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)             # forward only
            path.pop()
    backtrack(0)
    return results

Permutations:

def permute(nums):
    results, path = [], []
    used = [False] * len(nums)
    def backtrack():
        if len(path) == len(nums):
            results.append(path[:])
            return
        for i in range(len(nums)):       # always from 0
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False              # un-choose both pieces of state
    backtrack()
    return results

Note that the permutation version undoes two things, the path and the used flag. Any state you change before recursing has to be restored after. Forgetting one of them is the second most common bug in this pattern.

Handling duplicates in the input

When the input can contain repeated values, the same answer gets generated more than once. The fix is two lines and it is identical across Subsets II, Combination Sum II, and Permutations II:

nums.sort()                              # equal values become adjacent
...
    if i > start and nums[i] == nums[i - 1]:
        continue                         # skip repeats at this level only

The condition i > start is doing precise work. It allows a duplicate value to be used deeper in the path, where it represents a genuinely different answer, while blocking it from being chosen twice at the same level, where it would repeat a branch already explored. Sorting first is what makes the adjacency test valid, so it is not optional.

Want the whole family taught in order? The backtracking and subsets chapters of Grokking the Coding Interview build from Subsets through N-Queens and Sudoku with worked recursion traces and code in six languages, then do the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Subsets and Subsets II: the template, then the duplicate rule.
• Permutations and Permutations II: the used array, then the duplicate rule applied to it.
• Combination Sum: reuse is allowed, so recurse with i rather than i + 1. That one character is the whole difference, which makes it an excellent test of whether you hold the template or a memorized solution.
• Combination Sum II: each item used once, with duplicates in the input. Both rules at once.
• Letter Combinations of a Phone Number: choices come from a mapping rather than the input array, which is a useful reminder that "choices" is whatever the problem defines.
• Palindrome Partitioning: the choice is where to cut, and the validity check is whether the piece is a palindrome. Pruning matters here.
• Word Search: backtracking on a grid, where the un-choose step restores a cell you marked as visited.
• N-Queens: the classic. Without pruning it is far too slow, so track threatened columns and diagonals in sets and reject early.

The three mistakes that sink candidates

1. Appending path instead of path[:]. The single most common backtracking bug. You store a reference to a list that keeps changing, so all results end up identical or empty. Write the copy as you write the append.

2. Restoring only part of the state. If you set a used flag, mark a grid cell, or subtract from a remaining total before recursing, every one of those has to be undone after. Pair each mutation with its reversal on adjacent lines so the symmetry is visible.

3. Skipping duplicates without sorting. The nums[i] == nums[i-1] test only finds repeats if equal values are adjacent. Without the sort it silently misses some and the output contains duplicates.

A fourth worth naming: not pruning. Backtracking without validity checks explores the entire tree, and for N-Queens or Sudoku that means it never finishes. Ask what makes a partial path hopeless, and check for it before recursing.

Complexity, briefly

These problems are output-bound, so quote the size of the answer. Subsets is O(n · 2ⁿ) because there are 2ⁿ subsets and copying each costs O(n). Permutations is O(n · n!). N-Queens has no tidy closed form and is quoted as exponential with heavy pruning. Interviewers ask this to check that you understand you are enumerating, not searching, and that no clever trick makes exponential output smaller.

Practice ladder

In order, each rung adding one wrinkle.

1. Subsets (M): the template and the copy.
2. Combinations (M): stopping at a fixed size.
3. Permutations (M): the used array and double restoration.
4. Combination Sum (M): reuse, by recursing with i.
5. Subsets II (M): the duplicate-skip rule.
6. Combination Sum II (M): duplicates plus single use.
7. Letter Combinations of a Phone Number (M): choices from a mapping.
8. Palindrome Partitioning (M): validity as the pruning rule.
9. Word Search (M): backtracking over a grid.
10. N-Queens (H): pruning is required, not optional.
11. Stretch: Sudoku Solver (H), constraint propagation on top of the template.

Then write the tell in your own words ("I should suspect backtracking when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One template (choose, explore, un-choose), one copy that decides correctness (path[:]), one table that separates the three variants (loop start, reuse rule, record point), one two-line fix for duplicates (sort, then skip repeats at the same level), and one habit that keeps hard problems tractable (prune before you recurse). The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: Topological Sort, where ordering rules become a graph.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential backtracking problems in its 6-week plan.

FAQs

What is backtracking in simple terms? A recursive search that builds one candidate answer step by step. At each step it makes a choice, explores everything that follows from it, then undoes the choice so the next option can be tried from the same starting state. It is depth-first search over a tree of decisions, with the option to abandon branches that cannot work.

What is the difference between subsets, combinations, and permutations? Subsets records a result at every node and never reuses an earlier index. Combinations does the same but only records when the path reaches size k. Permutations loops from index 0 every time and uses a used array to avoid repeating an element, because order matters and [1,2] differs from [2,1].

Why does my backtracking solution return empty or identical results? You appended the path itself instead of a copy. The path is one list that is mutated throughout the search, so storing a reference means every result points at the same object. Use path[:] in Python or new ArrayList<>(path) in Java.

How do I avoid duplicate results when the input has repeated values? Sort the input first, then inside the loop skip any element equal to the previous one unless it is the first choice at this level, using if i > start and nums[i] == nums[i-1]: continue. That blocks repeated branches at the same depth while still allowing the value to be used further down the path.

When should I use dynamic programming instead of backtracking? When the question asks for a count or an optimum rather than the actual arrangements. Producing every combination that sums to a target is backtracking. Counting how many there are, or finding the smallest one, is usually dynamic programming, and our dynamic programming guide covers those families.