Backtracking with Pruning

Stop early when it can't work

Trying everything is slow. Pruning means giving up on a path as soon as you know it can't lead to a valid answer.

Combinations that add up to a target

def combination_sum(nums, target):
    nums.sort()
    result = []
    current = []

    def explore(start, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break                          # prune: the rest are even bigger
            current.append(nums[i])
            explore(i, remaining - nums[i])    # i, not i + 1: a number may be reused
            current.pop()

    explore(0, target)
    return result

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

Output

[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

N-Queens

Place N queens on an N × N chessboard so no two attack each other (same row, column or diagonal). Place one queen per row, and skip any column or diagonal that's already attacked:

def n_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    board = []
    solutions = []

    def place(row):
        if row == n:
            solutions.append(board[:])
            return
        for c in range(n):
            if c in cols or row - c in diag1 or row + c in diag2:
                continue                        # prune: attacked
            cols.add(c); diag1.add(row - c); diag2.add(row + c)
            board.append(c)
            place(row + 1)
            board.pop()
            cols.remove(c); diag1.remove(row - c); diag2.remove(row + c)

    place(0)
    return solutions

sols = n_queens(6)
print(len(sols), "solutions for 6 queens")
for c in sols[0]:
    print("." * c + "Q" + "." * (6 - c - 1))

Output

4 solutions for 6 queens
.Q....
...Q..
.....Q
Q.....
..Q...
....Q.

Tip: Cells on the same “\” diagonal share row − col; on the same “/” diagonal they share row + col. That makes the attack check O(1).