Lesson 12 of 16 Intervals, Greedy and Backtracking

Backtracking Pattern

Backtracking pattern with the choose, explore, un-choose template: subsets, permutations, combination sum with pruning, and N-Queens in Python.

45-55 min intermediate 0/16 lessons done
Course contents Lesson 12 of 16 · 0 done
On this page (8 sections)
  1. What you will learn
  2. Signals
  3. Template
  4. Code
  5. Handling duplicates
  6. Key takeaways
  7. Exercises
  8. Quiz

What you will learn

  • The choose / explore / un-choose template.
  • Subsets, permutations and combinations, and how they differ.
  • Pruning: cutting branches that can’t succeed.

Signals

  • “All”, “every”, “generate”, “list all possible” (subsets, permutations, partitions, valid boards).
  • Small constraints (n ≤ 10–20), because the output itself is exponential.

Template

def backtrack(state):
    if is_complete(state):
        record(copy_of(state))
        return
    for choice in choices(state):
        if not valid(choice, state):
            continue          # prune
        make(choice)          # choose
        backtrack(state)      # explore
        undo(choice)          # un-choose

Code

"""Backtracking: choose, explore, un-choose."""


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

    def dfs(i):
        if i == len(nums):
            out.append(path[:])
            return
        path.append(nums[i])   # choose nums[i]
        dfs(i + 1)
        path.pop()             # un-choose
        dfs(i + 1)             # skip nums[i]

    dfs(0)
    return out


def permutations(nums):
    out, path, used = [], [], [False] * len(nums)

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

    dfs()
    return out


def combination_sum(candidates, target):
    out, path = [], []
    candidates = sorted(candidates)

    def dfs(start, remaining):
        if remaining == 0:
            out.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                break  # prune: sorted, so every later candidate is too big as well
            path.append(c)
            dfs(i, remaining - c)  # i, not i + 1: a number may be reused
            path.pop()

    dfs(0, target)
    return out


def solve_n_queens(n):
    cols, diag, anti, count = set(), set(), set(), 0

    def place(row):
        nonlocal count
        if row == n:
            count += 1
            return
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue
            cols.add(c); diag.add(row - c); anti.add(row + c)
            place(row + 1)
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)

    place(0)
    return count


if __name__ == "__main__":
    print(subsets([1, 2, 3]))
    print(len(permutations([1, 2, 3, 4])), permutations([1, 2, 3])[:3])
    print(combination_sum([2, 3, 6, 7], 7))
    print([solve_n_queens(n) for n in range(4, 9)])

Output:

[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
24 [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
[[2, 2, 3], [7]]
[2, 10, 4, 40, 92]
  • Subsets: at each index, two branches: include or skip. 2ⁿ results.
  • Permutations: any unused element can go next; a used array tracks what’s taken. n! results.
  • Combination sum: start each loop at i (not i + 1) so numbers can repeat, and start from start so the same combination isn’t produced in different orders. Sorting enables the break prune.
  • N-Queens: three sets record attacked columns and diagonals (row - c and row + c are constant along each diagonal), making each validity check O(1). Counts for n = 4..8 are 2, 10, 4, 40, 92.

path[:] copies the path when recording. Appending path itself would record a reference that keeps changing, a very common bug.

Handling duplicates

When the input has duplicates (Subsets II, Permutations II), sort first and skip a choice equal to the previous one at the same depth: if i > start and nums[i] == nums[i-1]: continue.

Practise: backtracking problems.

Key takeaways

  • Backtracking = choose, explore, un-choose, with pruning before recursing.
  • Subsets branch include/skip; permutations pick any unused element; combinations move a start index forward.
  • Record copies of the path, not the path itself.
  • Sort to enable pruning and duplicate skipping.

Exercises

  1. Subsets II: subsets of a list with duplicates, without duplicate subsets.
  2. Word search in a grid (mark visited cells, restore on backtrack).
  3. Palindrome partitioning: all ways to split a string into palindromes.

Quiz

  1. Why does combination_sum recurse with i instead of i + 1?
  2. What goes wrong if you out.append(path) instead of path[:]?
  3. How does N-Queens check diagonals in O(1)?
Show answers
  1. Each candidate can be used unlimited times, so the same index stays available.
  2. All recorded entries are the same list object, which ends up empty after backtracking finishes.
  3. All cells on one diagonal share row - col, and on an anti-diagonal share row + col; sets of those values make the check O(1).

Finished this lesson?

Mark it complete to track your progress (saved in this browser).