Backtracking Algorithms: When and How to Use Them

Backtracking builds an answer one choice at a time. When a partial answer breaks a rule, it drops that answer and goes back to try the next choice. Problems that ask for every arrangement, selection, or placement that satisfies some rules are usually solved this way.

The Backtracking Pattern

The search runs over a tree whose root is an empty answer. Each level makes one decision, and each branch is one option for that decision. A path from the root to a leaf spells out one complete candidate. For permutations of [1, 2, 3], the first level picks the first number, the second picks one of the two that remain, and the six leaves are the six orderings.

The code walks this tree depth first with a single list for the partial answer. It appends on the way down and removes the last item on the way back up, so the list always matches the current path.

Permutations

Generate all permutations of an array.

def permute(nums):
    result = []
    
    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for num in nums:
            if num not in current:
                current.append(num)
                backtrack(current)
                current.pop()  # Backtrack
    
    backtrack([])
    return result

The line result.append(current[:]) stores a copy. Appending current itself stores a reference to the one list the whole search shares, and since every choice is undone by the end, the result for [1, 2, 3] comes back as six empty lists.

The check if num not in current also assumes the values are distinct. Given [1, 1, 2], it never lets the second 1 in, so nothing reaches length three and the result is empty. Tracking used positions fixes that, and one extra rule keeps repeated values from producing the same ordering twice.

def permute_unique(nums):
    nums = sorted(nums)
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            used[i] = False

    backtrack([])
    return result

After sorting, equal values sit side by side, and the skip rule places a copy only when the copy to its left is already in use. Equal values therefore always go in from left to right, so [1, 1, 2] gives each of its three orderings once.

Combinations

Generate combinations of k elements.

def combine(n, k):
    result = []
    
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()  # Backtrack
    
    backtrack(1, [])
    return result

The start parameter is what separates this from permutations. [1, 2] and [2, 1] are the same combination, so each level may only pick a number larger than the last one, which builds every combination once, in increasing order. Subsets use the same tree but record the current list at every node, including the empty root, which yields all 2ⁿ subsets. For [1, 2, 3] that is eight, counting the empty one.

def subsets(nums):
    result = []

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

    backtrack(0, [])
    return result

When fewer numbers remain from i to n than there are open slots, no branch from that point can finish. Changing the loop in combine to range(start, n - (k - len(current)) + 2) stops before those branches, and for n = 20 and k = 18 it cuts the recursive calls from just over a million to 1,330.

N-Queens Problem

Place n queens on an n by n board so that no two queens attack each other.

def solve_n_queens(n):
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check diagonals
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == 'Q':
                return False
        
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'  # Backtrack
    
    backtrack(0)
    return result

Each level picks the column for one row, so two queens never share a row, and is_safe checks only the rows above because the rows below are empty. A conflict ends a branch the moment its queen is placed. For n = 8 the search places a queen 2,056 times to find all 92 solutions, out of 16,777,216 ways to put one queen in each row.

Backtracking on a grid

Word Search asks whether a word can be spelled by moving between adjacent cells of a letter grid without reusing a cell. It resembles the grid search in the graph traversal guide, except that a traversal leaves a cell marked for good, while here a cell is off limits only for the current path and must be freed when the search backs out.

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

    def backtrack(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
            return False
        board[r][c] = "#"
        found = (backtrack(r + 1, c, i + 1) or backtrack(r - 1, c, i + 1) or
                 backtrack(r, c + 1, i + 1) or backtrack(r, c - 1, i + 1))
        board[r][c] = word[i]
        return found

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

On a board with rows AA and AB, the word ABAA exists, starting from the top right A. A version without the line that restores the letter first tries the top left A, fails, and leaves that cell marked, so the correct path finds its last letter blocked and the function returns False.

When to Use Backtracking

Phrases like "return all," "list every," and "generate all valid" ask for a collection of arrangements, which backtracking builds one at a time. With n! orderings or 2ⁿ subsets to list, the output alone grows too fast for large inputs, so small input limits, often around ten elements, are another clue. If a problem asks only how many ways there are, or for the single best answer, and the same partial states keep coming up, dynamic programming usually handles it without listing anything.

For a practice routine that makes these patterns habits, see LeetCode interview tips.