Recursion and Backtracking Patterns 2026: 18+ Problems [Solved]

Last Updated: June 2026

Why Backtracking is a High-Frequency Topic

Candidates report backtracking as appearing in roughly 15% of FAANG coding rounds and frequently in service company coding assessments. Based on public preparation resources and candidate-reported interview threads, the same 4 templates cover over 90% of backtracking questions asked.

The Backtracking Template

def backtrack(state, choices, result):
    # Base case: state is complete
    if is_complete(state):
        result.append(list(state))
        return

    for choice in choices:
        # Pruning: skip invalid choices
        if not is_valid(state, choice):
            continue

        # Make choice
        state.append(choice)

        # Recurse
        backtrack(state, next_choices(choices, choice), result)

        # Undo choice (backtrack)
        state.pop()

The three mandatory steps: make, recurse, undo. Forgetting the undo step is the most common bug.

Four Core Patterns

1. SUBSETS: all subsets of a set (2^n combinations)
2. PERMUTATIONS: all orderings of elements (n! orderings)
3. COMBINATIONS: choose k elements from n (nCk)
4. CONSTRAINT SATISFACTION: N-Queens, Sudoku (constraint-driven pruning)

Pattern 1: Subsets

def subsets(nums):
    """
    At each index: choose to include or exclude nums[i].
    Time: O(n * 2^n)  Space: O(n) for recursion stack
    """
    result = []

    def backtrack(start, current):
        result.append(list(current))

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

    backtrack(0, [])
    return result

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

Problem 1.1: Subsets II (With Duplicates)

Asked at: Amazon, Microsoft, Google

def subsets_with_dup(nums):
    """
    Sort first. Skip duplicate choices at the same level.
    Time: O(n * 2^n)  Space: O(n)
    """
    nums.sort()
    result = []

    def backtrack(start, current):
        result.append(list(current))

        for i in range(start, len(nums)):
            # Skip duplicate at same recursion level
            if i > start and nums[i] == nums[i - 1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

# Example
print(subsets_with_dup([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]]

Complexity: Time O(n * 2^n), Space O(n)

Pattern 2: Permutations

def permutations(nums):
    """
    At each position: place any unused element.
    Time: O(n! * n)  Space: O(n)
    """
    result = []

    def backtrack(current, used):
        if len(current) == len(nums):
            result.append(list(current))
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack(current, used)
            current.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result

# Example
print(permutations([1, 2, 3]))  # all 6 permutations

Problem 2.1: Permutations II (Duplicates)

Asked at: Amazon, Google

def permutations_unique(nums):
    """
    Sort. Skip duplicate element if previous identical element was not used.
    Time: O(n! * n)  Space: O(n)
    """
    nums.sort()
    result = []

    def backtrack(current, used):
        if len(current) == len(nums):
            result.append(list(current))
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            # Skip: same value as previous, previous was not used
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack(current, used)
            current.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result

Pattern 3: Combination Sum

Problem 3.1: Combination Sum (Unlimited Use)

Asked at: Amazon, Google, Microsoft, Adobe

def combination_sum(candidates, target):
    """
    Each candidate can be used unlimited times.
    Key: pass same start index to allow reuse.
    Time: O(n^(t/m)) where t=target, m=min candidate  Space: O(t/m)
    """
    result = []
    candidates.sort()

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(list(current))
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # pruning: sorted, no point continuing

            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])  # i, not i+1 (reuse allowed)
            current.pop()

    backtrack(0, [], target)
    return result

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

Complexity: Time O(n^(t/m)), Space O(t/m)

Problem 3.2: Combination Sum II (Each Number Used Once)

Asked at: Amazon, Microsoft

def combination_sum_2(candidates, target):
    """
    Each number used at most once. Skip duplicates at same level.
    Time: O(2^n)  Space: O(n)
    """
    candidates.sort()
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(list(current))
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i - 1]:
                continue  # skip duplicate at same level

            current.append(candidates[i])
            backtrack(i + 1, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return result

# Example
print(combination_sum_2([10, 1, 2, 7, 6, 1, 5], 8))  # [[1,1,6],[1,2,5],[1,7],[2,6]]

Problem 3.3: Combinations (Choose k from 1..n)

Asked at: Google, Amazon

def combine(n, k):
    """
    Choose k numbers from [1..n].
    Pruning: if remaining numbers insufficient, stop early.
    Time: O(k * C(n,k))  Space: O(k)
    """
    result = []

    def backtrack(start, current):
        if len(current) == k:
            result.append(list(current))
            return

        remaining_needed = k - len(current)
        for i in range(start, n - remaining_needed + 2):  # pruning
            current.append(i)
            backtrack(i + 1, current)
            current.pop()

    backtrack(1, [])
    return result

# Example
print(combine(4, 2))  # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Pattern 4: Constraint Satisfaction

Problem 4.1: N-Queens

Asked at: Google, Amazon, Adobe - classic constraint satisfaction

def solve_n_queens(n):
    """
    Place n queens on n x n board such that no two attack each other.
    Track occupied columns and diagonals for O(1) constraint checking.
    Time: O(n!)  Space: O(n)
    """
    result = []
    cols = set()
    diag1 = set()   # row - col
    diag2 = set()   # row + col

    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)

            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

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

# Example
solutions = solve_n_queens(4)
print(len(solutions))  # 2
print(solutions[0])

Complexity: Time O(n!), Space O(n)

Problem 4.2: Sudoku Solver

Asked at: Google, Amazon - hard constraint satisfaction

def solve_sudoku(board):
    """
    Try digits 1-9 for each empty cell. Backtrack on constraint violation.
    Time: O(9^(empty cells))  Space: O(1) (modifies board in-place)
    """
    def is_valid(board, row, col, num):
        # Check row
        if num in board[row]:
            return False
        # Check column
        if num in [board[r][col] for r in range(9)]:
            return False
        # Check 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for r in range(box_row, box_row + 3):
            for c in range(box_col, box_col + 3):
                if board[r][c] == num:
                    return False
        return True

    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 digit found
        return True  # all cells filled

    backtrack()

Complexity: Time O(9^81) worst case, practically much better due to constraint propagation

Problem 4.3: Word Search

Asked at: Amazon, Microsoft, Google, Adobe

def exist(board, word):
    """
    DFS backtracking on grid. Mark visited cells temporarily.
    Time: O(m * n * 4^L) where L = word length  Space: O(L)
    """
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]:
            return False

        temp = board[r][c]
        board[r][c] = '#'  # mark visited

        found = (backtrack(r+1, c, idx+1) or
                 backtrack(r-1, c, idx+1) or
                 backtrack(r, c+1, idx+1) or
                 backtrack(r, c-1, idx+1))

        board[r][c] = temp  # restore
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True

    return False

# Example
board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
print(exist(board, "ABCCED"))  # True
print(exist(board, "SEE"))     # True
print(exist(board, "ABCB"))    # False

Complexity: Time O(m * n * 4^L), Space O(L)

Problem 4.4: Generate Parentheses

Asked at: Amazon, Google, Microsoft, Facebook

def generate_parentheses(n):
    """
    At each step: add '(' if open < n, add ')' if close < open.
    Time: O(4^n / sqrt(n)) = Catalan number  Space: O(n)
    """
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(''.join(current))
            return

        if open_count < n:
            current.append('(')
            backtrack(current, open_count + 1, close_count)
            current.pop()

        if close_count < open_count:
            current.append(')')
            backtrack(current, open_count, close_count + 1)
            current.pop()

    backtrack([], 0, 0)
    return result

# Example
print(generate_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

Complexity: Time O(4^n / sqrt(n)), Space O(n)

Problem 4.5: Letter Combinations of Phone Number

Asked at: Amazon, Google, Microsoft, TCS

def letter_combinations(digits):
    """
    Map digit to letters, backtrack through positions.
    Time: O(4^n * n)  Space: O(n)
    """
    if not digits:
        return []

    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }

    result = []

    def backtrack(idx, current):
        if idx == len(digits):
            result.append(''.join(current))
            return

        for letter in phone_map[digits[idx]]:
            current.append(letter)
            backtrack(idx + 1, current)
            current.pop()

    backtrack(0, [])
    return result

# Example
print(letter_combinations("23"))
# ['ad','ae','af','bd','be','bf','cd','ce','cf']

Complexity: Time O(4^n * n), Space O(n)

Problem 4.6: Palindrome Partitioning

Asked at: Amazon, Google, Microsoft

def partition(s):
    """
    Backtrack: at each position, try all palindromic prefixes.
    Time: O(n * 2^n)  Space: O(n^2) for DP precomputation
    """
    n = len(s)
    result = []

    # Precompute palindrome table
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n - 1):
        is_pal[i][i + 1] = (s[i] == s[i + 1])
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j] and is_pal[i + 1][j - 1])

    def backtrack(start, current):
        if start == n:
            result.append(list(current))
            return

        for end in range(start, n):
            if is_pal[start][end]:
                current.append(s[start:end + 1])
                backtrack(end + 1, current)
                current.pop()

    backtrack(0, [])
    return result

# Example
print(partition("aab"))  # [['a','a','b'],['aa','b']]

Complexity: Time O(n * 2^n), Space O(n^2)

Complexity Quick Reference

Pattern Recognition

The Three Rules That Prevent Bugs

1. Sort before deduplication: Duplicate skipping only works after sorting.
2. Always undo your choice: Every append needs a matching pop().
3. Pass i vs i+1 correctly: Reuse allowed = pass i. Reuse not allowed = pass i+1.

Related Articles

• Dynamic Programming Patterns 2026
• Tree Traversal Patterns 2026
• Graph Traversal Patterns 2026
• Must-Do Coding Questions
• Backtracking Questions Placement