# Recursion and Backtracking Interview Patterns: Permutations, N-Queens, Sudoku

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

## Recursion and Backtracking Interview Patterns

Backtracking is systematic exhaustive search with pruning. It builds candidates incrementally and abandons (backtracks) as soon as it determines a candidate cannot lead to a valid solution. Essential for permutations, combinations, constraint satisfaction, and maze/grid problems.

## Backtracking Template


```
def backtrack(state, choices, result):
    # Base case: state is a valid complete solution
    if is_complete(state):
        result.append(state[:])   # copy current state
        return

    for choice in choices:
        if is_valid(state, choice):
            # Make choice
            state.append(choice)
            # Recurse
            backtrack(state, remaining_choices(choices, choice), result)
            # Undo choice (backtrack)
            state.pop()
```


## Pattern 1: Permutations


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

# Permutations with duplicates (sort + skip)
def perms_unique(nums):
    nums.sort()
    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
```


## Pattern 2: Combinations and Subsets


```
# All subsets (power set)
def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(current[:])   # add current state at every node
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

# Combinations of size k
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(1, [])
    return result

# Combination sum (elements can repeat, target sum)
def combination_sum(candidates, target):
    candidates.sort()
    result = []
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break  # pruning
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])  # i (not i+1) allows reuse
            current.pop()
    backtrack(0, [], target)
    return result
```


## Pattern 3: N-Queens

Place N queens so none attack each other. Track column and diagonal occupancy:


```
def solve_n_queens(n):
    result = []
    cols = set()
    diag1 = set()  # (row - col) constant on  diagonal
    diag2 = set()  # (row + col) constant on / diagonal

    def backtrack(row, board):
        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'
            backtrack(row + 1, board)
            cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)
            board[row][col] = '.'

    board = [['.']*n for _ in range(n)]
    backtrack(0, board)
    return result
```


## Pattern 4: Word Search on Grid


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


## Pattern 5: Sudoku Solver


```
def solve_sudoku(board):
    def is_valid(board, row, col, num):
        box_r, box_c = 3 * (row // 3), 3 * (col // 3)
        return (
            num not in board[row] and
            num not in [board[r][col] for r in range(9)] and
            num not in [board[box_r+r][box_c+c] for r in range(3) for c in range(3)]
        )
    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for num in '123456789':
                        if is_valid(board, r, c, num):
                            board[r][c] = num
                            if backtrack(): return True
                            board[r][c] = '.'
                    return False  # no valid number found
        return True  # all cells filled
    backtrack()
```


## Classic Backtracking Problems

| Problem | State | Branching Factor | Pruning |
| --- | --- | --- | --- |
| Permutations | Current sequence | n-k remaining | Skip used elements |
| Subsets | Current subset | n-i remaining | None (collect all) |
| Combination Sum | Current sum | Candidates ≤ remaining | Sort + break early |
| N-Queens | Row placement | n columns | Col/diagonal sets |
| Word Search | Grid position | 4 directions | Bounds + visited |
| Sudoku Solver | Board state | 9 digits | Row/col/box constraints |
| Palindrome Partition | Current partition | Remaining suffixes | Only palindrome splits |

## Interview Tips

- Always draw the decision tree for 2-3 levels before coding

- The three steps: make a choice, recurse, undo the choice (backtrack)

- Pruning is the key to performance — identify invalid states early

- For permutations with duplicates: sort first, skip nums[i] == nums[i-1] when nums[i-1] not used

- Time complexity: O(branching_factor^depth) in the worst case, much better with pruning

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

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

- [Atlassian Interview Guide](https://techinterview.org/atlassian-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/)

🏢 Asked at: [Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering](https://techinterview.org/uber-interview-guide/)