Backtracking Interview Patterns: Subsets, Permutations, N-Queens, and Constraint Satisfaction (2025)

Backtracking Template

Backtracking = DFS + undo. The universal template: choose (add to path), recurse (explore), unchoose (remove from path). Always ask: what are the choices at each step? What is the base case? What constraint prunes the search? Pruning is what separates backtracking from brute-force: eliminate branches early when a partial solution cannot possibly lead to a valid complete solution. Time complexity without pruning: O(k^n) where k=choices, n=depth. Good pruning can reduce this dramatically in practice.

def backtrack(path, choices):
    if is_complete(path):
        result.append(path[:])  # copy, not reference
        return
    for choice in choices:
        if is_valid(path, choice):    # PRUNE invalid choices
            path.append(choice)       # CHOOSE
            backtrack(path, next_choices(path, choice))  # RECURSE
            path.pop()                # UNCHOOSE (undo)

Subsets with and without Duplicates

# Subsets (LC 78): no duplicates in input
def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    def bt(start, path):
        result.append(path[:])  # add at every node, not just leaves
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1, path)
            path.pop()
    bt(0, [])
    return result

# Subsets II (LC 90): input has duplicates
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    def bt(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            # Skip duplicates at the same level
            if i > start and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            bt(i + 1, path)
            path.pop()
    bt(0, [])
    return result

Permutations with and without Duplicates

# Permutations (LC 46): no duplicates
def permute(nums: list[int]) -> list[list[int]]:
    result = []
    def bt(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            bt(path, used)
            path.pop()
            used[i] = False
    bt([], [False] * len(nums))
    return result

# Permutations II (LC 47): input has duplicates
def permute_unique(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    def bt(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            # Skip duplicate: same value as previous AND previous not used
            # (if previous was used, we are in a different branch - allow)
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(nums[i])
            bt(path, used)
            path.pop()
            used[i] = False
    bt([], [False] * len(nums))
    return result

Combination Sum

# Combination Sum (LC 39): reuse elements, find all combos summing to target
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    result = []
    candidates.sort()
    def bt(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # sorted: no point continuing
            path.append(candidates[i])
            bt(i, path, remaining - candidates[i])  # i (not i+1): reuse allowed
            path.pop()
    bt(0, [], target)
    return result

# Combination Sum II (LC 40): each element used at most once, has duplicates
def combination_sum2(candidates, target):
    candidates.sort()
    result = []
    def bt(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break
            if i > start and candidates[i] == candidates[i-1]: continue  # skip dup
            path.append(candidates[i])
            bt(i + 1, path, remaining - candidates[i])
            path.pop()
    bt(0, [], target)
    return result

N-Queens

def solve_n_queens(n: int) -> list[list[str]]:
    result = []
    cols = set()
    diag1 = set()  # row - col (top-left to bottom-right diagonal)
    diag2 = set()  # row + col (top-right to bottom-left diagonal)

    def bt(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  # attacked
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            board[row][col] = 'Q'
            bt(row + 1, board)
            board[row][col] = '.'; cols.remove(col)
            diag1.remove(row-col); diag2.remove(row+col)

    board = [['.'] * n for _ in range(n)]
    bt(0, board)
    return result
# Key insight: use sets for O(1) attack checking instead of O(n) scan

Meta coding interviews test backtracking extensively. See common patterns for Meta interview: backtracking and combinatorics problems.

Atlassian coding rounds include backtracking problems. Review patterns for Atlassian interview: backtracking and search problems.

Apple coding interviews test backtracking and N-Queens style problems. See patterns for Apple interview: backtracking and constraint satisfaction.