Recursion & Backtracking: Permutations, Combinations & Subsets
Master the art of generating all possibilities — permutations, combinations, subsets, N-Queens, and Sudoku. Learn the backtracking template that solves them all.
The Backtracking Template
Backtracking is controlled recursion. At each step, you make a choice, recurse, then undo the choice (backtrack). This explores all valid configurations without building the full search tree in memory. The template: (1) check if current state is a solution, (2) for each possible next choice, make it, recurse, undo it.
Subsets (Power Set)
def subsets(nums: list[int]) -> list[list[int]]:
"""Generate all subsets of a list."""
result = []
def backtrack(start: int, current: list[int]):
result.append(current[:]) # Add a copy of current subset
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop() # Backtrack
backtrack(0, [])
return result
# With duplicates: sort first, skip consecutive duplicates
def subsets_with_dups(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
def backtrack(start: int, current: list[int]):
result.append(current[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # Skip duplicates
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return resultPermutations
def permutations(nums: list[int]) -> list[list[int]]:
"""Generate all permutations."""
result = []
def backtrack(current: list[int], remaining: set):
if not remaining:
result.append(current[:])
return
for num in list(remaining):
current.append(num)
remaining.remove(num)
backtrack(current, remaining)
remaining.add(num) # Backtrack
current.pop() # Backtrack
backtrack([], set(nums))
return resultCombinations
def combinations(n: int, k: int) -> list[list[int]]:
"""Generate all combinations of k numbers from 1 to n."""
result = []
def backtrack(start: int, current: list[int]):
if len(current) == k:
result.append(current[:])
return
# Pruning: need (k - len(current)) more elements
for i in range(start, n - (k - len(current)) + 2):
current.append(i)
backtrack(i + 1, current)
current.pop()
backtrack(1, [])
return result
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
"""Find all combinations that sum to target (reuse allowed)."""
result = []
def backtrack(start: int, remaining: int, current: list[int]):
if remaining == 0:
result.append(current[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
current.append(candidates[i])
backtrack(i, remaining - candidates[i], current) # i, not i+1 (reuse)
current.pop()
backtrack(0, target, [])
return resultThe key differences: Subsets — collect at every node. Permutations — collect at leaves, track used elements. Combinations — collect at leaves, move forward only (no revisiting). All three use the same backtrack-undo pattern.
N-Queens: Classic Backtracking
def solve_n_queens(n: int) -> list[list[str]]:
"""Place n queens on an n×n board so no two attack each other."""
solutions = []
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def backtrack(row: int, board: list[list[str]]):
if row == n:
solutions.append(["".join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
board[row][col] = "Q"
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1, board)
board[row][col] = "."
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
board = [["." for _ in range(n)] for _ in range(n)]
backtrack(0, board)
return solutionsPruning is the difference between a fast backtracking solution and a slow one. Always check constraints before recursing — this cuts branches early and dramatically reduces the search space.