Recursion II: Backtracking & Divide and Conquer

Recursion II: Backtracking & Divide and Conquer | Algoryva

First, the naive way

Generate every placement, then check

Place n queens on an n × n board so none attacks another. The blunt way: write down one column for every row (n choices each, so n^n boards), then check each board for attacks.

For 4 queens that is 256 boards, fine. For 8 queens it is 16,777,216 boards, and for 12 it is about 9 × 10¹². The method wastes almost all its time finishing boards that were already hopeless after the first two queens.

python

from itertools import product

def queens_bruteforce(n):
    count = 0
    for cols in product(range(n), repeat=n):       # a column for every row: n ** n placements
        ok = all(cols[i] != cols[j] and abs(cols[i] - cols[j]) != j - i
                 for i in range(n) for j in range(i + 1, n))
        if ok:
            count += 1
    return count

print(queens_bruteforce(4))   # 2
print(queens_bruteforce(5))   # 10

Cost: O(nⁿ × n²): every complete placement is generated and checked, however early the conflict appeared.

Worked by hand

The search tree for subsets of {1, 2, 3}

At each element there are two choices: skip it or take it. The path of choices *is* the subset.

choice for 1	choice for 2	choice for 3	subset
skip	skip	skip	[]
skip	skip	take	[3]
skip	take	skip	[2]
skip	take	take	[2, 3]
take	skip	skip	[1]
take	skip	take	[1, 3]
take	take	skip	[1, 2]
take	take	take	[1, 2, 3]

1
Eight leaves
Three yes/no choices give 2³ = 8 leaves. n items give 2ⁿ subsets, which is why enumeration is limited to small n.
2
Reading the output order
Code that tries “skip” before “take” visits leaves in exactly the order of this table. The order of results depends on the order you try the choices.

Implementation

Subsets: take it or leave it

Each recursive call decides about one element. The path.pop() after the second call is the un-choose step.

Plan in plain steps

pseudocode

go(i):
    if i is past the last element: record a copy of path; return
    go(i + 1)                    # leave nums[i] out
    path.append(nums[i]); go(i + 1); path.pop()   # put nums[i] in, then take it back out

python

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

    def go(i):
        if i == len(nums):
            res.append(path[:])
            return
        go(i + 1)                  # choice 1: skip nums[i]
        path.append(nums[i])       # choice 2: take nums[i]
        go(i + 1)
        path.pop()                 # undo the choice

    go(0)
    return res

print(subsets([1, 2, 3]))   # [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
print(len(subsets(list(range(10)))))   # 1024

Reading the code

›res.append(path[:]) stores a copy. If you append path itself, every stored result would be the same list, finally empty after all the pops.
›go(i + 1) first with nothing added is the “skip” branch; then add, recurse, remove for the “take” branch.
›After path.pop() the state is exactly as it was on entry, so the caller can continue.
›There are 2ⁿ results, so n = 10 gives 1,024 and n = 20 about a million: enumeration cost, not a flaw of the method.

Implementation

Combinations, and pruning

To choose k numbers from 1 to n, loop over the next number to add, and recurse with a start just past it so each combination appears once, in increasing order. Pruning removes starts that cannot possibly leave enough numbers.

python

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

    def go(start):
        if len(path) == k:
            res.append(path[:])
            return
        for x in range(start, n + 1):
            path.append(x)
            go(x + 1)
            path.pop()

    go(1)
    return res

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

    def go(start):
        if len(path) == k:
            res.append(path[:])
            return
        need = k - len(path)
        for x in range(start, n - need + 2):     # not enough numbers left beyond this point
            path.append(x)
            go(x + 1)
            path.pop()

    go(1)
    return res

print(combine(4, 2))   # [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
print(combine(6, 3) == combine_pruned(6, 3))   # True
print(len(combine(10, 5)))   # 252

Reading the code

›go(x + 1) means the next number must be larger, so [1, 2] and [2, 1] are not both produced.
›In combine_pruned, need = k - len(path) numbers are still required, and the last start that leaves enough room is n - need + 1, hence the range end n - need + 2. Without pruning the loop would start branches that can never reach size k.
›Pruning does not change the answer (the equality check prints True), only the work.
›There are C(10, 5) = 252 combinations of 5 from 10.

Implementation

Permutations: use each item once

For orderings, every position may take any item not yet used. A boolean list used records which are taken, and must be restored on the way back.

python

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

    def go():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            go()
            path.pop()
            used[i] = False

    go()
    return res

print(permutations([1, 2, 3]))   # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
print(len(permutations([1, 2, 3, 4])))   # 24

Reading the code

›used[i] = True and used[i] = False are the choose and un-choose pair for the extra state, next to append and pop. Restoring *both* is essential.
›for i in range(len(nums)) tries every item as the next element, skipping those already used.
›The count is n! (24 for four items, 3,628,800 for ten), so this is only for small n.
›itertools.permutations does the same in the standard library; write your own when the problem adds pruning rules.

Implementation

Reuse, sorted pruning, and duplicates

Two small changes handle common variations. Reuse: recurse with the same index (i) instead of i + 1 so a number may be picked again. Duplicates in the input: sort, then skip a value equal to the previous one at the same decision position, so identical branches are not explored twice.

python

def combination_sum(cands, target):
    cands = sorted(cands)
    res, path = [], []

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

    go(0, target)
    return res

print(combination_sum([2, 3, 6, 7], 7))   # [[2, 2, 3], [7]]
print(combination_sum([2, 3, 5], 8))   # [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
print(combination_sum([2], 1))   # []

def subsets_with_dup(nums):
    nums = sorted(nums)
    res, path = [], []

    def go(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                         # skip a repeated value at the same position
            path.append(nums[i])
            go(i + 1)
            path.pop()

    go(0)
    return res

print(subsets_with_dup([1, 2, 2]))   # [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

Reading the code

›In combination_sum, sorting lets us break as soon as one candidate exceeds the remainder: every later one is at least as big, so the whole rest of the loop is pruned.
›go(i, remain - cands[i]) passes i, not i + 1, which allows the same number again, but never goes backwards to a smaller index, so [2, 3] and [3, 2] are not both produced.
›In subsets_with_dup, i > start and nums[i] == nums[i - 1] skips a repeated value only when it would start the *same* branch as its twin, while still allowing both copies in one subset ([1, 2, 2]).
›combination_sum([2], 1) is an example with no answer: the result is simply an empty list.

Implementation

N-Queens with fast conflict checks

Checking every earlier queen for each square is slow. Instead, keep sets of the used columns and diagonals. Squares on the same diagonal share row − col (one direction) or row + col (the other).

python

def count_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    count = 0

    def go(r):
        nonlocal count
        if r == n:
            count += 1
            return
        for c in range(n):
            if c in cols or r - c in diag1 or r + c in diag2:
                continue                          # attacked: prune this whole branch
            cols.add(c)
            diag1.add(r - c)
            diag2.add(r + c)
            go(r + 1)
            cols.remove(c)
            diag1.remove(r - c)
            diag2.remove(r + c)

    go(0)
    return count

print(count_queens(4), count_queens(6), count_queens(8))   # 2 4 92

Reading the code

›c in cols or r - c in diag1 or r + c in diag2 is the pruning test: three set lookups, O(1) each.
›The six lines adding and removing from the sets are the choose and un-choose pair. Every set that was changed is restored.
›nonlocal count lets the inner function update the outer variable.
›Known counts: 2 solutions for n = 4, 4 for n = 6, 92 for n = 8. Brute force at n = 8 tests 16.7 million boards; backtracking visits only a few thousand partial boards.

Implementation

Divide and conquer: a balanced tree from a sorted list

Make a balanced binary search tree from a sorted list. The middle item is the root; the left half builds the left subtree and the right half builds the right subtree. Each half is the same problem, smaller.

python

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def build(a, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    if lo >= hi:
        return None
    mid = (lo + hi) // 2
    return Node(a[mid], build(a, lo, mid), build(a, mid + 1, hi))

def inorder(n):
    return [] if n is None else inorder(n.left) + [n.val] + inorder(n.right)

def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))

root = build([1, 2, 3, 4, 5, 6, 7])
print(root.val, root.left.val, root.right.val)   # 4 2 6
print(inorder(root))   # [1, 2, 3, 4, 5, 6, 7]
print(height(root), height(build(list(range(1, 1001)))))   # 3 10

Reading the code

›The base case lo >= hi is an empty range, which becomes None.
›The recursive calls pass index ranges instead of slicing, so no copying happens: O(n) time overall.
›Because the root is always the middle, both sides have nearly equal size, so the height is about log₂ n: 3 for 7 items and 10 for 1,000.
›Inorder of the result is the original sorted list, which confirms the BST property.

Implementation

Divide and conquer: a recursively built string

Define S₁ = "0" and Sᵢ = Sᵢ₋₁ + "1" + reverse(invert(Sᵢ₋₁)), where invert flips every bit. Find the k-th character of Sₙ without building the huge string. The length is 2ⁿ − 1, so building it is hopeless for large n, but the structure tells you which part of the string position k is in.

python

def find_kth_bit(n, k):
    if n == 1:
        return "0"
    length = (1 << n) - 1
    mid = (length + 1) // 2
    if k == mid:
        return "1"
    if k < mid:
        return find_kth_bit(n - 1, k)
    mirrored = find_kth_bit(n - 1, length - k + 1)
    return "0" if mirrored == "1" else "1"

print(find_kth_bit(3, 1))   # 0
print(find_kth_bit(4, 11))   # 1
print("".join(find_kth_bit(4, k) for k in range(1, 16)))   # 011100110110001

Reading the code

›Position mid (the middle) is always "1". A position in the left half equals the same position in Sₙ₋₁, so recurse on it.
›A position in the right half is the mirror image, inverted: it corresponds to position length − k + 1 of Sₙ₋₁ with the bit flipped.
›Only one recursive call is made per level, so the cost is O(n), not O(2ⁿ).
›The last line builds S₄ by asking for each of its 15 characters, and matches the string written out by hand: 011100110110001.

Worked problem

Count the N-Queens solutions

The problem

Count the ways to place n queens on an n × n board so that no two attack each other.

Place queens row by row: exactly one per row is forced, so the decision at each level is *which column*.
A column is allowed if it is not already in cols and its two diagonals (r − c, r + c) are not in the diagonal sets.
Choose a column, recurse to the next row, then undo all three set updates.
A full board (row == n) counts as one solution.

python

def count_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    count = 0

    def go(r):
        nonlocal count
        if r == n:
            count += 1
            return
        for c in range(n):
            if c in cols or r - c in diag1 or r + c in diag2:
                continue                          # attacked: prune this whole branch
            cols.add(c)
            diag1.add(r - c)
            diag2.add(r + c)
            go(r + 1)
            cols.remove(c)
            diag1.remove(r - c)
            diag2.remove(r + c)

    go(0)
    return count

print(count_queens(4), count_queens(6), count_queens(8))   # 2 4 92

Takeaway. Three sets turn the attack check into O(1) lookups, and the row-by-row order removes the “one queen per row” rule from the search entirely. The same shape (a row per level, columns as choices, sets for conflicts) solves Sudoku-type puzzles.

Worked problem

Find the k-th bit of a huge recursive string

The problem

The strings are built by S₁ = "0" and Sᵢ = Sᵢ₋₁ + "1" + reverse(invert(Sᵢ₋₁)). Return the k-th character of Sₙ (1-indexed). n can be large enough that Sₙ could not be stored.

Do not build the string. Sₙ has length 2ⁿ − 1 and a clear shape: left copy, a single "1" in the middle, then the mirrored and inverted copy.
If k is the middle, the answer is "1". If k is in the left half, ask the same question of Sₙ₋₁.
If k is in the right half, its mirror position is length − k + 1 in Sₙ₋₁, and the answer is the *opposite* bit of that.
Only one branch is followed per level: n steps.

python

def find_kth_bit(n, k):
    if n == 1:
        return "0"
    length = (1 << n) - 1
    mid = (length + 1) // 2
    if k == mid:
        return "1"
    if k < mid:
        return find_kth_bit(n - 1, k)
    mirrored = find_kth_bit(n - 1, length - k + 1)
    return "0" if mirrored == "1" else "1"

print(find_kth_bit(3, 1))   # 0
print(find_kth_bit(4, 11))   # 1
print("".join(find_kth_bit(4, k) for k in range(1, 16)))   # 011100110110001

Takeaway. When a structure is defined recursively, you can often answer a question about one element by recursing into just the relevant part. The work drops from the size of the structure (2ⁿ) to its recursion depth (n).

Wrap-up

Remember this

Backtracking builds an answer one choice at a time and undoes a choice when it leads nowhere: choose, explore, un-choose.
Store a copy of the path when you record a result, and restore every piece of state after the recursive call.
Pruning abandons hopeless branches early and is what makes puzzles like N-Queens feasible.
Subsets, combinations and permutations differ only in which choices are allowed at each step; duplicates need sorting plus a skip rule.
Divide and conquer splits a problem into independent smaller copies and combines their answers; often only one part needs exploring.

Cheat sheet

Template: base case: record path[:]; for each valid choice: choose, recurse, un-choose
Subsets / permutations / combinations: 2ⁿ / n! / C(n, k) results
Combinations: recurse with start = x + 1 so each set appears once
Duplicates: sort; skip nums[i] == nums[i−1] when i > start
Prune: reject a partial answer as soon as it cannot succeed
Divide and conquer: split, solve independent halves, combine; recursion depth log n

Top traps to avoid

Appending the live path to the results.
Forgetting to un-choose, or restoring only some of the state.
Starting the loop at 0 every time for combinations.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.In the backtracking template, what is the purpose of the un-choose step?
2.How many subsets does a set of 10 items have?
3.Why must a result be recorded as path[:] rather than path?
4.“Return all ways to arrange these 4 distinct letters” suggests:
5.In subsets_with_dup, what does if i > start and nums[i] == nums[i - 1]: continue prevent?
6.Backtracking N-Queens with pruning is much faster than generating all n^n placements because:
7.How many subsets does [1, 2] have, counted with itertools.combinations for every size?
8.How many permutations does [1, 2, 3] have? Print len(list(permutations(...))).
9.Count the placements of 4 non-attacking queens on a 4x4 board (try every column permutation). What is printed?
10.A divide-and-conquer max over [3, 9, 2, 7]: what does it print?
11.What does pruning mean in backtracking?
12.How many subsets does a set of n items have, and what is the time to list them all?
13.Why must backtracking undo a choice after the recursive call returns?
14.Count combinations of [1, 2, 3] (no repeats, any size) whose sum is exactly 3.
15.Recursive digit sum: def ds(n): return 0 if n == 0 else n % 10 + ds(n // 10). What is ds(1234)?

After this lesson you will be able to

Builds on

Unlocks

A maze with chalk

Generate every placement, then check

Stop the moment a partial answer is already wrong

The backtracking template

4-Queens: place, fail, backtrack

The search tree for subsets of {1, 2, 3}

Subsets: take it or leave it

Reading the code

Combinations, and pruning

Reading the code

Permutations: use each item once

Reading the code

Reuse, sorted pruning, and duplicates

Reading the code

N-Queens with fast conflict checks

Reading the code

Divide and conquer: split, solve, combine

Divide and conquer: a balanced tree from a sorted list

Reading the code

Divide and conquer: a recursively built string

Reading the code

Costs

Edge cases

Mistakes to avoid

How to spot backtracking and divide and conquer

Count the N-Queens solutions

Find the k-th bit of a huge recursive string

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core49 problems

Application6 problems

Challenge2 problems