Backtracking

Take the subsets of [1, 2]: first decide whether to take 1, then decide whether to take 2. Following one path to the end gives one subset; then you go back to the most recent branch point and try the other choice there. That "go to the end, come back, try another" is backtracking. Combinations and permutations work the same way; they only change two things: what this level decides, and which choices are still available.

Two principles run through the whole article:

1. Draw the recursion tree first: how many levels, how many branches per level. Each level is one decision, and the branches are the ways to make it. Read the complexity straight off the tree: roughly branch^level leaves, times the cost of recording an answer at each leaf.
2. Whatever you take, you give back. Whatever you added to the path (or used set, or board) before going down must be removed exactly before you move on to the next branch at this level. The state on the path always equals "the choices made on the way from the root to this node".

The article goes in this order, and each step adds exactly one idea to the previous one:

When to Use This Pattern

When a problem asks for "all solutions", brute force means listing every combination of choices. The number of answers is itself exponential (n elements have 2ⁿ subsets), so there's no polynomial algorithm; all you can do is list them cleanly and avoid wasted work.

The hard part is that the number of choices depends on the input: picking k numbers takes k nested for loops, and you can't write that when k is an input. The recursion tree solves exactly this: each level of recursion is one for loop, and the input decides how many levels there are. Take the subsets of nums = [1, 2, 3]: three levels, each deciding whether one element is in:

Each row is one root-to-leaf path. DFS walks one at a time with the path in a single list; after finishing one it undoes the last choice and tries the next, so the extra space is only the tree height, O(n). Constraints can be checked halfway: a branch already known to be invalid isn't entered, rather than being thrown away at the leaf.

Recognition Checklist

• The problem wants every solution (subsets, permutations, combinations, cuts, placements), not a count or a single optimum
• A solution is built step by step, each step choosing one of a finite set of candidates
• The input is small (n around 20 or less), so exponential time is acceptable
• Some constraint can fail partway through (bracket counts, queen conflicts, the sum already exceeds target)
• You need a path in a grid or graph, and the same point can't be used twice on one path

Before You Code

Before writing code, sketch the first two levels of the recursion tree on paper and answer these three questions:

1. How many levels, and what does each level represent? What level i decides: whether to take element i, who goes in position i, which column the queen in row i takes. The number of levels is usually known before you write any code, and it's the recursion's stopping condition.
2. How many branches per level? Which ones are invalid as soon as you'd enter them? How many ways there are to make this decision. Invalid branches are cut before entering.
3. What do you take, how do you give it back, and where do you record answers? Whatever you add to the path, used set, or board, you remove after the recursive call returns. Answers are recorded at leaves, or at every node. Record a copy, path[:]; Step 1 explains why.

Questions 1 and 2 together give the complexity: branch^level leaves. Question 3 decides the shape of the code: every branch is the three lines "take, recurse, give back".

Try it on LC 22 Generate Parentheses. The problem: given a positive integer n, return every valid string made of n ( and n ). "Valid" means that reading left to right, no prefix has more ) than (. For example, n = 3 has 5 answers: ((())), (()()), (())(), ()(()), ()()(). What follows doesn't check a given string; it generates these 5.

• Levels: the final string has 2n = 6 characters, each level decides whether one position gets ( or ), so 6 levels.
• Branches: 2, but not both are always valid. Placing ( needs fewer than n ( so far; placing ) needs fewer ) than ( so far, otherwise the prefix has too many closing brackets and nothing later can fix it.
• Take / give back / record: append one character to the path, pop it on return; record at the leaf once all 6 are placed. Without pruning there are 2⁶ = 64 leaves; with pruning only 5 are left.

Step 5 turns this into code.

Subsets (LeetCode 78)

Given distinct integers, return every subset as a value list, including the empty subset, in any order. Use each position at most once; positions need not be contiguous. Choosing the same values in another order does not create a new subset.

Input: nums = [1, 2]. Expected: [[1, 2], [1], [2], []] (any order).

Recursion tree: level i only decides whether to take nums[i], so every node has two branches; i == len(nums) is a leaf. path holds what was taken on the way from the root to the current node; res collects a copy of it at each leaf.

1. Walk it by hand

2. Read the rules off the table

• Only leaves (i == len(nums)) record, and they record a copy of path.
• Every level has two branches: first "take" (append → recurse → pop), then "skip" (just recurse).
• Each pop puts path back to what it was when the level was entered, so the "skip" branch sees a clean path.

3. Turn each row into code

def subsets(nums):
    res, path = [], []
    def dfs(i):
        if i == len(nums):
            res.append(path[:])
            return
        path.append(nums[i])
        dfs(i + 1)
        path.pop()
        dfs(i + 1)
    dfs(0)
    return res

Core Templates

All six steps use the same approach: answer the three questions, draw the recursion tree, then check against the two principles — are the level and branch counts right, and does every "take" have a matching "give back"?

Step 1: One element per level, take it or skip it

Problem: return all subsets of an array (LC 78).

Given an integer array nums with distinct elements, return all of its subsets, including the empty set, in any order.

For example, [1, 2] → [[], [1], [2], [1, 2]]. Subsets ignore order: [1, 2] and [2, 1] are the same subset and appear once.

The three questions:

• Levels: n, where level i only considers nums[i]. i == n means every element has been decided: a leaf.
• Branches: 2, take it or skip it.
• Take / give back / record: when taking, append, and pop after the recursive call; when skipping, add nothing and go straight down. Record a copy at each leaf.

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

    def dfs(i):                     # level i: decide whether to take nums[i]
        if i == len(nums):
            res.append(path[:])     # only a leaf is a complete subset; path[:] is a fresh copy
            return
        path.append(nums[i])        # take: include nums[i]
        dfs(i + 1)
        path.pop()                  # give back: restore this level's state
        dfs(i + 1)                  # skip nums[i]

    dfs(0)
    return res


assert subsets([1, 2]) == [[1, 2], [1], [2], []]   # the example above, in a different order
assert subsets([]) == [[]]
assert len(subsets([1, 2, 3, 4])) == 16

dfs is defined inside subsets, so it can read and modify the outer res and path. It only calls their methods (append, pop) and never rebinds those names, so no nonlocal is needed.

Execution order of subsets([1, 2]):

n levels, 2 branches each, 2ⁿ leaves, an O(n) copy per leaf: O(2ⁿ · n) total. Stack depth and path length are both O(n).

What if you don't give back? Drop the path.pop(), and when level 0 takes the "skip 1" branch the path still holds the 1 and 2 taken by the previous branch:

The result is [[1, 2], [1, 2], [1, 2, 2], [1, 2, 2]]: wrong answers, and [1], [2], [] are missing. Writing the "skip" branch before the "take" branch doesn't let you drop the pop either: when you return to the level above, the extra element in the path leaks into that level's next branch.

Why record path[:]. The whole search has exactly one path object, and every take and give back modifies it. A Python list is stored by reference: res.append(path) puts into res not "what path contains right now" but "the path object itself". All four recordings add the same object, so every later change to path shows up in all four entries of res. When the search ends, path has been emptied, so res becomes [[], [], [], []].

path[:] is a slice: it takes every element from start to end and builds a new list. It's a snapshot at the moment of recording, and nothing done to path afterwards changes it. list(path) or path.copy() do the same. Strings are immutable, so when the path holds characters, "".join(path) already produces a snapshot and needs no further copy.

Variation: pass the state as a parameter and there's nothing to give back (LC 1863)

Given an array nums of positive integers. For each subset, XOR (^) all of its numbers together to get that subset's "XOR total"; the empty subset's XOR total is 0. Return the sum of the XOR totals of all subsets.

For example, [1, 3] has four subsets, [], [1], [3], [1, 3], with XOR totals 0, 1, 3, and 1 ^ 3 = 2, which add up to 6. Equal values at different indices are different choices. The subsets themselves aren't returned.

Think first: Do you need to store each subset in full this time? If all you need is "the XOR of the elements taken so far", does that value still have to live in a shared path and be given back on return?

def subset_xor_sum(nums):
    def dfs(i, cur):                # cur: XOR of the taken elements, passed down as a parameter
        if i == len(nums):
            return cur              # leaf: one subset's XOR total
        return dfs(i + 1, cur ^ nums[i]) + dfs(i + 1, cur)    # take + skip

    return dfs(0, 0)


assert subset_xor_sum([1, 3]) == 6          # the example above
assert subset_xor_sum([5, 1, 6]) == 28
assert subset_xor_sum([]) == 0

Step 1 recap

• What it solves: listing all subsets. Each level decides one element, with two branches: take or skip.
• The key line: record at the leaf with res.append(path[:]), a copy, not path itself.
• What the variations change: LC 1863 doesn't need the subsets, only an integer, so the state moves from the shared path into the parameter cur, and the give-back step disappears.
• Easiest mistake: res.append(path) without copying, which leaves res full of the same emptied list. Whenever you record a mutable object, record a copy.

Step 1 has exactly two branches per level. When picking k numbers or building a sum, each level picks "the next one" from the remaining candidates and the number of branches isn't fixed: that's Step 2.

Step 2: The branches are a for loop, picking from start onward

Problem: Combination Sum (LC 39).

Given an array candidates of distinct positive integers and a positive integer target. Each number can be used any number of times. Return every combination that sums to target. Combinations ignore order: [2, 2, 3] and [3, 2, 2] are the same and appear once. Return [] if there is none.

For example, candidates = [2, 3, 6, 7], target = 7 → [[2, 2, 3], [7]].

"All positive" matters: every number taken makes remain, the amount still missing, strictly smaller, so the recursion always stops. If 0 were allowed, you could take 0 forever and the tree would have no bottom.

This is making change with coins. The most direct tree is: each level takes one coin, and the branch is which kind. With candidates = [2, 3] and target = 7, taking 2 then 3, and taking 3 then 2, reach the same combination [2, 3, ...] in a different order.

The fix is "never look back": each level may only pick from the position the previous level chose, onward. Then the numbers in every combination appear in increasing index order, and each combination has only one way to be written. The three questions:

• Levels: not fixed; reaching target (remain == 0) is a leaf.
• Branches: each of candidates[start:]. Passing i down means the same number can be used again; passing i + 1 means once used, it's done.
• Take / give back / record: append the number, recurse, pop. Record when remain == 0. After sorting, once a number exceeds remain, the larger ones after it don't need trying.

def combination_sum(candidates, target):
    cands, res, path = sorted(candidates), [], []   # sorted returns a new, sorted list

    def dfs(start, remain):         # the next number may only come from cands[start:]; remain is what's still missing
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(cands)):
            if cands[i] > remain:
                break               # sorted, so the rest are only larger
            path.append(cands[i])
            dfs(i, remain - cands[i])   # pass i: the same number can be reused
            path.pop()

    dfs(0, target)
    return res


assert combination_sum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]    # the example above
assert combination_sum([2, 3, 5], 8) == [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
assert combination_sum([2], 1) == []

With candidates = [2, 3] and target = 7, what you pass down decides the result:

Variation: a different tree — each level considers one kind of coin (LC 39)

Still LC 39, same input and output. This time draw it differently: level i only considers the coin candidates[i].

Think first: When each level handles one kind of coin, what are the branches at that level? How many are there, and what decides it? Drawn this way, can a reordered duplicate like [2, 3, 2] still appear? A branch takes in several numbers at once; how many does it have to give back?

def combination_sum_by_count(candidates, target):
    res, path = [], []

    def dfs(i, remain):             # level i: decide how many of candidates[i] to use
        if i == len(candidates):
            if remain == 0:
                res.append(path[:])
            return
        c = candidates[i]
        for k in range(remain // c + 1):    # branches: use 0, 1, ..., remain // c
            path.extend([c] * k)            # [c] * k is k copies of c; extend appends them one by one
            dfs(i + 1, remain - k * c)
            del path[len(path) - k:]        # took k, so delete the last k

    dfs(0, target)
    return res


assert sorted(combination_sum_by_count([2, 3, 6, 7], 7)) == [[2, 2, 3], [7]]
assert sorted(combination_sum_by_count([2, 3, 5], 8)) == [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
assert combination_sum_by_count([2], 1) == []

One step further: Combinations (LC 77)

Given positive integers n and k, return every way to choose k distinct numbers from 1 to n, in any order.

For example, n = 4, k = 2 → [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]].

Compared with Combination Sum, each number is used once here, and the stopping condition is "k numbers chosen" instead of "the sum equals target".

Think first: After choosing x, do you pass down x or x + 1? If the path already holds 2 numbers and needs 1 more, and x is already n, is there any point in trying further? How large can x get?

def combine(n, k):
    res, path = [], []

    def dfs(start):
        if len(path) == k:
            res.append(path[:])
            return
        for x in range(start, n - (k - len(path)) + 2):   # x goes up to n - need + 1; skip when too few numbers remain
            path.append(x)
            dfs(x + 1)              # x + 1: each number used once
            path.pop()

    dfs(1)
    return res


assert combine(4, 2) == [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]   # the example above
assert combine(3, 3) == [[1, 2, 3]]
assert combine(1, 1) == [[1]]
assert combine(3, 0) == [[]]
assert [c for c in combine(9, 3) if sum(c) == 7] == [[1, 2, 4]]          # LC 216: 3 numbers from 1..9 summing to 7

One step further: subsets written as a for loop (LC 78)

Still LC 78: return all subsets of nums (distinct elements). For example, [1, 2] → [[], [1], [1, 2], [2]], in any order.

Think first: Take combine from the previous problem and drop the len(path) == k stopping condition. What does each level of this tree decide? Is the path at every node a valid subset? Then where should answers be recorded?

def subsets_loop(nums):
    res, path = [], []

    def dfs(start):
        res.append(path[:])         # every node is a subset; record on entry
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1)
            path.pop()

    dfs(0)
    return res


assert subsets_loop([1, 2]) == [[], [1], [1, 2], [2]]      # the example above
assert subsets_loop([]) == [[]]
assert sorted(subsets_loop([1, 2, 3])) == sorted(subsets([1, 2, 3]))

Variation: each level matches one position of the input (LC 17)

Given a string digits containing only 2 through 9. Each digit on a phone keypad maps to a few letters: 2 is abc, 3 is def, …, 7 is pqrs, 9 is wxyz. Pick one letter for each digit and join them in the original order. Return every string that can be formed, in any order. Digits can't be skipped or reordered.

For example, "23" → ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. The code below returns [] for an empty string.

Think first: How many levels are there? What does level i decide? Where do this level's branches come from? Is start still needed?

def letter_combinations(digits):
    phone = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
             "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
    if not digits:
        return []
    res, path = [], []

    def dfs(i):                     # level i: which letter digits[i] becomes
        if i == len(digits):
            res.append("".join(path))   # join the character list into one string; strings are immutable, no copy needed
            return
        for ch in phone[digits[i]]:     # iterating a string yields one letter at a time
            path.append(ch)
            dfs(i + 1)
            path.pop()

    dfs(0)
    return res


assert letter_combinations("23") == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]   # the example above
assert letter_combinations("7") == ["p", "q", "r", "s"]
assert letter_combinations("") == []

Variation: splitting a string (LC 131)

Given a nonempty string s, cut it into pieces so that every piece is a palindrome (reads the same forwards and backwards). Return every way to cut it; each way is a list of substrings in the original order that join back into exactly s.

For example, "aab" → [["a", "a", "b"], ["aa", "b"]]. This isn't just finding the longest palindrome, and characters can't be skipped.

Think first: What does each level decide? What does start mean this time? What are this level's branches, and which ones do you go down? When is the string fully cut?

def partition(s):
    res, path = [], []

    def dfs(start):                 # s[:start] is already cut
        if start == len(s):
            res.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):    # branch: the next piece is s[start:end]
            piece = s[start:end]
            if piece == piece[::-1]:                # piece[::-1] is the string reversed
                path.append(piece)
                dfs(end)
                path.pop()

    dfs(0)
    return res


assert partition("aab") == [["a", "a", "b"], ["aa", "b"]]   # the example above
assert partition("a") == [["a"]]
assert len(partition("aaaa")) == 8

Variation: Word Break II (LC 140)

Given a string s and a word list word_dict. Insert spaces into s to split it into words, each of which must be in word_dict; a word may be used more than once. Return every way to split it, each as a sentence with words joined by single spaces, in any order. If s can't be split completely, return [].

For example, "catsanddog" with ["cat", "cats", "and", "sand", "dog"] → ["cat sand dog", "cats and dog"].

Think first: Compared with palindrome partitioning, does the shape of the tree change? Which check gets replaced? What's different about recording an answer?

def word_break(s, word_dict):
    words, res, path = set(word_dict), [], []   # a set gives O(1) average lookup

    def dfs(start):
        if start == len(s):
            res.append(" ".join(path))  # join the words with single spaces
            return
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in words:   # go down only if the piece is a word
                path.append(s[start:end])
                dfs(end)
                path.pop()

    dfs(0)
    return res


assert word_break("catsanddog", ["cat", "cats", "and", "sand", "dog"]) == ["cat sand dog", "cats and dog"]   # the example above
assert word_break("pineapple", ["apple", "pen", "applepen", "pine", "pineapple"]) == ["pine apple", "pineapple"]
assert word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) == []

Step 2 recap

• What it solves: combinations, target sums, and splits, where each level picks "the next one" from the remaining candidates.
• The key line: for i in range(start, len(cands)), plus passing down i (reusable) or i + 1 (single use).
• What the variations change: the other tree switches the branch from "which one" to "how many of this kind"; LC 77 stops at "k chosen" and cuts branches with too few numbers left; subsets move recording from the leaves to every node; LC 17's branches are the letters of this digit; LC 131 and LC 140 branch on "where the next piece ends" and differ only in what counts as a valid piece.
• Easiest mistake: starting the for loop at 0. It looks back, and the same combination reappears in other orders, e.g. [2, 2, 3], [2, 3, 2], [3, 2, 2].

Combinations and splits rely on start to "never look back". Permutations are the opposite: a different order is a different answer, so Step 3 draws the tree another way.

Step 3: Each level decides who goes in one position

Problem : return all permutations of an array ( LC 46 ). (Pro lesson)

Step 3 recap

What it solves : listing all permutations. Each level decides who goes in one position, and the branches are every element not used yet. (Pro lesson)

Step 4: Within one level, one branch per distinct value

Problem : return all subsets when the input may contain duplicates, with no duplicate subsets in the result ( LC 90 ). (Pro lesson)

One step further: deduplicating on the Step 1 tree (LC 90)

Still LC 90 : the input may have duplicates and the subsets must not. (Pro lesson)

One step further: Combination Sum II (LC 40)

Given an array candidates of positive integers (which may contain equal values) and a positive integer target . (Pro lesson)

One step further: permutations with duplicates (LC 47)

Given an integer array nums that may contain equal values, return all distinct permutations, in any order. (Pro lesson)

Step 4 recap

What it solves : keeping results free of duplicates when the input has duplicate values. (Pro lesson)

Step 5: Check constraints before entering a branch

Problem : generate all valid combinations of parentheses ( LC 22 ), the example worked through in "Before You Code". (Pro lesson)

One step further: N-Queens (LC 51)

Given a positive integer n, place n queens on an n × n board so that no two attack each other: no two in the same row, the same column, or o… (Pro lesson)

One step further: partition into k equal-sum subsets (LC 698)

Given an array nums of positive integers and an integer k (1 ≤ k ≤ array length). (Pro lesson)

One step further: Matchsticks to Square (LC 473)

Given positive integers, the lengths of matchsticks. Every stick must be used and none can be broken. (Pro lesson)

Step 5 recap

What it solves : when solutions must satisfy constraints, check before entering a branch, so an invalid node's whole subtree is never walked… (Pro lesson)

Step 6: visited means "on the current path"

Problem : Word Search ( LC 79 ). Given a 2D grid of letters board and a string word . (Pro lesson)

One step further: Android unlock patterns (LC 351)

Nine dots in a 3 × 3 grid, numbered 1 to 9 row by row: An unlock pattern is a sequence of distinct dots, with a line drawn between each pair… (Pro lesson)

Step 6 recap

What it solves : finding paths in a grid or graph that satisfy a condition, where a point can't be used twice on one path. (Pro lesson)

The six steps together

Step Representative problem Each level represents Branches Levels Order of magnitude Step 1 78 Subsets element i 2 (take / skip) n O(2ⁿ · n)… (Pro lesson)

One Problem, Many Disguises

LC 93 Restore IP Addresses, from the table, says: given a string of digits, insert three dots to split it into four parts that form a valid… (Pro lesson)

Common Pitfalls

Recording with res.append(path) . It stores references to the same list, which ends up emptied: subsets([1, 2]) returns [[], [], [], []] . (Pro lesson)

Say It in the Interview

Explain the recursion tree first, what each level is, how many branches, how many levels, and the complexity follows. (Pro lesson)