NOA Labs
Algorithms Lesson 11 of 14 ⏱️ 5 min read

Backtracking: Subsets, Permutations & N-Queens

The backtracking template — choose, explore, un-choose — applied to subsets, permutations and N-Queens, with pruning.

Updated Oct 30, 2026

What is backtracking?

Backtracking is a way to explore every possible solution by building it one choice at a time, and undoing the last choice when it leads to a dead end. It's a depth-first search over a tree of decisions.

Think of solving a maze: walk forward, and when you hit a wall, step back to the last junction and try another path. Backtracking solves problems such as:

  • Generating all subsets, permutations or combinations
  • Puzzles: N-Queens, Sudoku, crosswords
  • Searching a grid for a word, finding paths
  • Constraint problems: scheduling, colouring a map

The backtracking template

Almost every backtracking solution follows the same shape — choose, explore, un-choose:

Plaintext
def backtrack(path, choices):
    if path is a complete solution:
        record a copy of path
        return
    for choice in choices:
        if choice is not valid: continue       # pruning
        path.append(choice)                    # 1. choose
        backtrack(path, remaining choices)     # 2. explore
        path.pop()                             # 3. un-choose (backtrack)

The un-choose step restores the state so the next iteration starts clean. Forgetting it is the most common backtracking bug.

Subsets (the power set)

Every element is either in or out, so n elements have 2^n subsets. At each level we decide which element to add next, only moving forward to avoid duplicates:

Python
def subsets(nums):
    result, path = [], []

    def backtrack(start):
        result.append(path[:])            # every partial path is a valid subset (copy it!)
        for i in range(start, len(nums)):
            path.append(nums[i])          # choose
            backtrack(i + 1)              # explore with the remaining elements
            path.pop()                    # un-choose

    backtrack(0)
    return result

print(subsets([1, 2, 3]))

Output:

Plaintext
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Note path[:] — appending path itself would store a reference that later becomes empty.

Complexity: O(n · 2^n) time — 2^n subsets, each up to n long to copy.

Permutations

For permutations, order matters and each element is used exactly once, so we track which ones are already used:

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

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i, value in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(value)
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

print(permutations([1, 2, 3]))

Output:

Plaintext
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Complexity: O(n · n!) — there are n! permutations.

Find all combinations of candidates (reusable) that add up to a target. Pruning — stopping early when a branch can't succeed — makes backtracking practical:

Python
def combination_sum(candidates, target):
    candidates.sort()
    result, path = [], []

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

    backtrack(0, target)
    return result

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

Output:

Plaintext
[[2, 2, 3], [7]]

N-Queens

Place n queens on an n × n chessboard so that no two attack each other (same row, column or diagonal). We place one queen per row and track attacked columns and diagonals in sets for O(1) checks:

  • Cells on the same diagonal share row - col.
  • Cells on the same anti-diagonal share row + col.
Python
def solve_n_queens(n):
    solutions, queens = [], []                 # queens[row] = column of the queen in that row
    cols, diag, anti = set(), set(), set()

    def backtrack(row):
        if row == n:
            solutions.append(["".join("Q" if c == q else "." for c in range(n)) for q in queens])
            return
        for col in range(n):
            if col in cols or row - col in diag or row + col in anti:
                continue                       # prune: this square is attacked
            queens.append(col); cols.add(col); diag.add(row - col); anti.add(row + col)
            backtrack(row + 1)
            queens.pop(); cols.remove(col); diag.remove(row - col); anti.remove(row + col)

    backtrack(0)
    return solutions

for line in solve_n_queens(4)[0]:
    print(line)
print("solutions for n = 1..8:", [len(solve_n_queens(n)) for n in range(1, 9)])

Output:

Plaintext
.Q..
...Q
Q...
..Q.
solutions for n = 1..8: [1, 0, 0, 2, 10, 4, 40, 92]

Without pruning we'd try 8^8 ≈ 16.7 million placements for n = 8; with it, the search visits only a few thousand states.

Recognising backtracking problems

Clue in the problem Likely approach
"Return all subsets / permutations / combinations" Backtracking
"Find all valid arrangements / placements" Backtracking with pruning
"Count the number of ways" with large inputs Probably dynamic programming instead
"Find the minimum / maximum" Often DP or greedy; backtracking + pruning if inputs are tiny

Backtracking is exponential by nature, so it's appropriate when input sizes are small (typically n ≤ 20) or pruning is very effective.

Common mistakes

  • Forgetting to un-choose (pop(), used[i] = False) after the recursive call.
  • Appending path instead of path[:] — every stored result ends up as the same (empty) list.
  • Generating duplicates — use a start index for combinations, or sort and skip equal neighbours when input has duplicates.
  • No pruning — checking validity only at the end explodes the running time.

Key takeaways

  • Backtracking = DFS over choices: choose, explore, un-choose.
  • Subsets use a start index; permutations use a used array.
  • Pruning invalid branches early is what makes backtracking fast enough.
  • Expect exponential complexity — use it for small inputs or when all solutions are required.
Finished this lesson?
Tick it off to track your Algorithms progress.
Next lesson