# Backtracking Algorithm Interview Patterns: Subsets, Permutations, N-Queens, Word Search

Source: https://www.techinterview.org/post/3233462922/backtracking-algorithm-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## Backtracking Algorithm Patterns

Backtracking is a systematic way to enumerate all possible solutions by building candidates incrementally and abandoning (pruning) partial candidates the moment they cannot lead to a valid solution. It is the go-to technique for constraint satisfaction problems, permutations, combinations, and puzzle solving.

- [Coinbase Interview Guide](https://techinterview.org/coinbase-software-engineer-interview/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)

## The Universal Backtracking Template


```
def backtrack(state, choices):
    if is_solution(state):
        result.append(state.copy())
        return
    for choice in choices:
        if is_valid(state, choice):
            make_choice(state, choice)
            backtrack(state, remaining_choices(choices, choice))
            undo_choice(state, choice)   # backtrack
```

The key insight: always undo (restore) state after recursing. This is what distinguishes backtracking from plain DFS.

## Pattern 1: Subsets


```
def subsets(nums):
    result = []
    def bt(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            bt(i + 1, current)
            current.pop()
    bt(0, [])
    return result
```

Time: O(2^N * N) — 2^N subsets, each takes O(N) to copy. The start index ensures each element is considered only once, preventing duplicates.

## Pattern 2: Permutations


```
def permutations(nums):
    result = []
    def bt(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            bt(current, remaining[:i] + remaining[i+1:])
            current.pop()
    bt([], nums)
    return result
```

Time: O(N! * N). For duplicates: sort first, skip if nums[i] == nums[i-1] and nums[i-1] not used. Use a visited boolean array to track used indices.

## Pattern 3: Combinations


```
def combinations(n, k):
    result = []
    def bt(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        # Pruning: not enough elements remaining
        remaining = n - start + 1
        needed = k - len(current)
        if remaining < needed: return
        for i in range(start, n + 1):
            current.append(i)
            bt(i + 1, current)
            current.pop()
    bt(1, [])
    return result
```

The pruning condition "if remaining < needed: return" is critical — it cuts branches where there are not enough numbers left to fill the combination.

## Pattern 4: N-Queens


```
def solve_n_queens(n):
    result = []
    cols = set(); diag1 = set(); diag2 = set()
    board = [['.' for _ in range(n)] for _ in range(n)]
    def bt(row):
        if row == n:
            result.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
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            board[row][col] = 'Q'
            bt(row + 1)
            board[row][col] = '.'
            cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)
    bt(0)
    return result
```

The three sets track occupied columns and diagonals. Row-col identifies the "/" diagonal; row+col identifies the "" diagonal. This gives O(1) conflict checking.

## Pattern 5: Word Search


```
def exist(board, word):
    rows, cols = len(board), len(board[0])
    def bt(r, c, idx):
        if idx == len(word): return True
        if r = rows or c = cols: return False
        if board[r][c] != word[idx]: return False
        temp, board[r][c] = board[r][c], '#'  # mark visited
        found = (bt(r+1,c,idx+1) or bt(r-1,c,idx+1) or
                 bt(r,c+1,idx+1) or bt(r,c-1,idx+1))
        board[r][c] = temp  # restore
        return found
    for r in range(rows):
        for c in range(cols):
            if bt(r, c, 0): return True
    return False
```


## When to Use Backtracking

  - Enumerate all solutions: subsets, permutations, combinations

  - Constraint satisfaction: Sudoku, N-Queens, crossword fill

  - Puzzle solving: maze traversal with revisit restriction, word search

  - Partition problems: partition to equal subset sum, palindrome partitioning

## Pruning Strategies

  - Feasibility check: if current path cannot lead to solution (length exceeded, constraint violated), return early

  - Sort input: enables stopping early when value exceeds target (combination sum with duplicates)

  - Constraint propagation: N-Queens column/diagonal sets for O(1) validity checks