DSA course menu
Backtracking Algorithms in Python: Subsets, Permutations and N-Queens
Learn backtracking: choose, explore, un-choose. Generate subsets, permutations and combinations, solve N-Queens and combination sum, and prune the search to make it faster.
On this page
Backtracking builds a solution one choice at a time. After each choice it explores further; when a path cannot lead to a valid answer (or has been fully explored), it undoes the last choice and tries the next option. It is depth-first search over the tree of all possible choices.
Every backtracking solution follows the same three steps:
- Choose: add an option to the current partial solution.
- Explore: recurse to make the next choice.
- Un-choose: remove the option again, so the next option starts from a clean state.
Subsets#
Every item is either in or out of a subset, so n items have 2ⁿ subsets:
def subsets(items):
result, current = [], []
def build(i):
if i == len(items):
result.append(current[:]) # save a copy
return
current.append(items[i]) # choose: include items[i]
build(i + 1) # explore
current.pop() # un-choose
build(i + 1) # explore without it
build(0)
return result
print(subsets(["a", "b", "c"]))
print(len(subsets(list(range(10)))))[['a', 'b', 'c'], ['a', 'b'], ['a', 'c'], ['a'], ['b', 'c'], ['b'], ['c'], []]
1024current[:] saves a copy: current keeps changing as the search continues, so appending the list itself would leave every saved entry pointing at the same (finally empty) list.
Permutations#
A permutation uses every item once, in some order: n! of them. Choose any unused item for the next position:
def permutations(items):
result, current, used = [], [], [False] * len(items)
def build():
if len(current) == len(items):
result.append(current[:])
return
for i, x in enumerate(items):
if not used[i]:
used[i] = True # choose
current.append(x)
build() # explore
current.pop() # un-choose
used[i] = False
build()
return result
print(permutations([1, 2, 3]))[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Python's itertools.permutations and itertools.combinations generate these directly; writing them by hand is how you learn the pattern used for harder problems.
Combination sum, with pruning#
Find all combinations of candidate numbers (each usable many times) that add up to a target.
Pruning means stopping a branch early when it cannot succeed. With the candidates sorted, once one is too big, every later one is too big too:
def combination_sum(candidates, target):
candidates = sorted(candidates)
result, current = [], []
calls = 0
def build(start, remaining):
nonlocal calls
calls += 1
if remaining == 0:
result.append(current[:])
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining:
break # prune: the rest are bigger
current.append(c)
build(i, remaining - c) # i, not i + 1: c can be reused
current.pop()
build(0, target)
return result, calls
print(combination_sum([2, 3, 6, 7], 7))
print(combination_sum([2, 3, 5], 8))([[2, 2, 3], [7]], 10)
([[2, 2, 2, 2], [2, 3, 3], [3, 5]], 13)Starting each loop at start (not 0) means combinations are built in non-decreasing order, so [2, 2, 3] is found once instead of also as [2, 3, 2] and [3, 2, 2].
N-Queens#
Place N queens on an N × N chessboard so that no two attack each other (same row, column or diagonal).
Place one queen per row. For each row, try every column that is not attacked; sets make the attack check O(1). Cells on the same \ diagonal share row - col; on the same / diagonal they share row + col.
def solve_queens(n):
solutions = []
cols, diag1, diag2 = set(), set(), set()
placement = []
def place(row):
if row == n:
solutions.append(placement[:])
return
for col in range(n):
if col in cols or row - col in diag1 or row + col in diag2:
continue # attacked: prune
cols.add(col); diag1.add(row - col); diag2.add(row + col)
placement.append(col)
place(row + 1)
placement.pop()
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
place(0)
return solutions
first = solve_queens(6)[0]
for col in first:
print(" ".join("Q" if c == col else "." for c in range(6)))
print([len(solve_queens(n)) for n in range(1, 9)]). Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .
[1, 0, 0, 2, 10, 4, 40, 92]The last line counts the solutions for boards of size 1 to 8; there are 92 ways to place 8 queens.
Cost#
Backtracking explores a tree of choices, so its cost is usually exponential: O(2ⁿ) for subsets, O(n!) for permutations. That is unavoidable when the output itself is that big. Pruning cannot change the worst case, but it often removes most of the tree in practice. When the same subproblem appears again and again, dynamic programming is the better tool.
Common mistakes#
Practice#
Practice exercise
Write letter_combinations(digits) that returns all strings a phone number could spell, using the keypad 2 = "abc", 3 = "def", 4 = "ghi", 5 = "jkl", 6 = "mno", 7 = "pqrs", 8 = "tuv", 9 = "wxyz".
Show hint
Recurse over the positions of digits. At each position, loop over the letters for that digit, append one, recurse, and pop it. An empty input has no combinations.
Show solution
KEYS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
def letter_combinations(digits):
if not digits:
return []
result, current = [], []
def build(i):
if i == len(digits):
result.append("".join(current))
return
for letter in KEYS[digits[i]]:
current.append(letter)
build(i + 1)
current.pop()
build(0)
return result
print(letter_combinations("23"))
print(len(letter_combinations("79")))['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
167 and 9 both have four letters, so "79" gives 4 × 4 = 16 combinations.
Key takeaway#
Next: when taking the best-looking option is always right, in Greedy Algorithms.
Finished this lesson?