Backtracking in Python: Subsets, Permutations, Combination Sum and Word Search

Backtracking is a way of trying every possible answer without writing a separate loop for each choice. You build a solution one step at a time, and the moment a step cannot lead to a valid answer you undo it and try the next option. It is the standard approach for subsets, permutations, combinations, puzzles and path search in a grid. This guide gives you one reusable template and applies it to six problems, each with code that was run and checked against the sample inputs.

The choose, explore, undo template

Almost every backtracking solution has the same shape. You keep a path that holds the choices made so far. At each step you loop over the available choices, add one to the path, recurse, and then remove it again so the next choice starts from a clean state.

def backtrack(state):
    if is_complete(state):
        results.append(copy_of(state))   # always store a copy
        return
    for choice in available_choices(state):
        if not is_valid(choice, state):
            continue                      # prune early
        apply(choice, state)              # choose
        backtrack(state)                  # explore
        undo(choice, state)               # undo

Think of it as a depth-first search over a tree of decisions. The recursion depth is the number of decisions, and pruning cuts off whole branches that cannot succeed. If recursion on trees is new to you, read tree and graph traversals first.

Subsets (LeetCode 78)

Return every subset of a list of distinct numbers. Every node in the decision tree is itself a valid answer, so we record the path on entry rather than waiting for a base case. The start index makes sure we only move forward, which stops us from producing the same subset in a different order.

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

    def backtrack(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return res

For [1, 2, 3] the output is [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3], which is all 8 subsets. There are 2ⁿ subsets and copying each one costs up to n, so time is O(n · 2ⁿ). The recursion uses O(n) space apart from the output.

Permutations (LeetCode 46)

Here order matters, so a forward-only start index is wrong. Instead, any unused element can go in any position. A used list records which elements are already in the path.

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

    def backtrack():
        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])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return res

For [1, 2, 3] you get all 6 orderings, from [1,2,3] to [3,2,1]. Time is O(n · n!) because there are n! results of length n.

Combination Sum (LeetCode 39)

Find all combinations of candidates that add up to a target, where each number may be reused. Reuse is handled by recursing with i instead of i + 1. Sorting the candidates lets us stop the loop as soon as a number is too large, which is a simple but effective prune.

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

    def backtrack(start, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                     # later numbers are even larger
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return res

For [2, 3, 6, 7] and target 7 the answer is [2,2,3] and [7]. The running time is exponential in the worst case and depends on the target and the smallest candidate, so describe it as bounded by the size of the decision tree rather than quoting a tidy formula.

Subsets II: handling duplicates (LeetCode 90)

If the input contains repeated values, such as [1, 2, 2], the plain subsets code would output [1, 2] twice. Sort first, then skip a value when it equals the previous one at the same level of the tree.

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

    def backtrack(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                  # same value already tried here
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return res

The condition i > start is the part people get wrong. It allows the second 2 to be used after the first 2 is already in the path, but blocks it from starting a new branch at the same position. The result for [1, 2, 2] is [], [1], [1,2], [1,2,2], [2], [2,2].

Generate Parentheses (LeetCode 22)

Produce every well-formed string of n pairs of parentheses. Instead of generating all strings and filtering, only allow moves that keep the string valid: add an opening bracket while fewer than n are used, and add a closing bracket only if it would not exceed the openings.

def generate_parentheses(n):
    res = []

    def backtrack(cur, opened, closed):
        if len(cur) == 2 * n:
            res.append(''.join(cur))
            return
        if opened < n:
            cur.append('(')
            backtrack(cur, opened + 1, closed)
            cur.pop()
        if closed < opened:
            cur.append(')')
            backtrack(cur, opened, closed + 1)
            cur.pop()

    backtrack([], 0, 0)
    return res

For n = 3 the five results are ((())), (()()), (())(), ()(()) and ()()(). The number of results is the nth Catalan number (5 for n = 3, 14 for n = 4), so the work grows quickly but far more slowly than the 2²ⁿ strings you would check by brute force.

Word Search (LeetCode 79)

Backtracking also works on grids. Starting from each cell, follow the word letter by letter through the four neighbours. A cell may not be reused in the same path, so mark it as visited before exploring and restore it afterwards.

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i]:
            return False
        tmp = board[r][c]
        board[r][c] = '#'                 # mark visited
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        board[r][c] = tmp                 # undo
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

On the board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], the word ABCCED is found and ABCB is not, because the second B would need the first B’s cell again. Time is O(m · n · 3^L) for an m by n grid and a word of length L, since after the first letter each step has at most three new directions.

Choosing the right variant

Common mistakes

• Appending path itself to the results. The list keeps changing, so every stored answer ends up empty. Always append path[:] or list(path).
• Forgetting to undo a choice, which leaves stale data for the next branch.
• Using start for permutations, or skipping it for combinations, which gives wrong or repeated results.
• Not sorting before skipping duplicates, so equal values are not adjacent.
• Pruning too late. Check validity before recursing, not after.

Quick answers

When in doubt

If the problem says all possible, every valid or list all, start with the template above and decide which of the three questions applies: do I move forward only, do I track what is used, or do I need to skip duplicates. If the problem only asks how many ways or the best value, look at dynamic programming instead. A weekly practice schedule is in the 30-day study plan.

Also see: bit manipulation tricks and tries for related patterns.