Top 10 Backtracking Problems for LeetCode Interviews (Easy to Hard)

Backtracking shows up in roughly one out of every four coding interview loops. Not because companies love recursion, but because it probes something specific: can you reason about state that mutates as you go deeper and restores as you come back up? That mental model is the whole job.

The theory is easy. The implementation bugs are embarrassing. result.append(path) instead of result.append(path[:]) is a one-character mistake that makes every collected answer an empty list by the time the algorithm finishes. Your code runs. No error. Just a list of empty lists looking back at you. Backtracking finds new ways to betray you.

These ten problems are ordered by structural complexity. Each one teaches something the previous one didn't. Work through them in sequence and you'll recognize the variant in front of you before you write a single line.

One Template, Every Variation

Every backtracking problem runs on the same skeleton. The constraints change. The structure doesn't.

def backtrack(start, path):
    # collect or check base case
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1, path)   # i+1, i, or 0+used[]. This one decision changes everything
        path.pop()

The single variable that separates Subsets, Permutations, and Combination Sum: the loop start. Pass i + 1 to prevent reuse. Pass i to allow reuse. Start from 0 with a used[] array when order matters. Everything else stays structurally identical.

Before the problems: always copy path when you collect results. result.append(path) stores a reference to a live list you're actively mutating. By the time the recursion unwinds, every entry in result points to the same empty list. result.append(path[:]) takes a snapshot. That one-character fix is responsible for more interview saves than any clever algorithm choice. Write it once. Write it correctly.

1. Subsets (LC 78): Every Node Is an Answer

Difficulty: Medium.

The non-obvious thing: collect at every node, not just the leaves.

Most people come into Subsets expecting to harvest answers at the bottom of the tree, because that's how every other backtracking problem works. Subsets refuses. The empty path is a valid subset. So is [1]. So is [1, 2, 3]. You collect before the loop, not inside a base-case branch.

def subsets(nums):
    result, path = [], []
    def backtrack(start):
        result.append(path[:])          # every node, not just leaves
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()
    backtrack(0)
    return result

The tree below shows why. Every node is a valid subset, including the root. Collection happens on the way in, not at the leaves.

Backtracking recursion tree for subsets([1,2,3]) showing collection at every node, not just leaves

Every node is an answer. The blue dots mark where you collect. That's all of them.

Time: O(n·2^n). The n factor comes from copying path, not from traversing the tree. See backtracking time complexity for the full derivation.

2. Permutations (LC 46): When Order Changes the Loop

Difficulty: Medium.

Swap the start index for a used[] array the moment order starts mattering.

With subsets, [1, 2] and [2, 1] are the same answer and you skip one. With permutations they're different, so both need to appear. A start index prevents revisiting earlier elements, which is exactly what you need for subsets and exactly what you don't need here. Replace it with a boolean array. Restart from 0 each call.

def permute(nums):
    result, path, used = [], [], [False] * len(nums)
    def backtrack():
        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])
            backtrack()
            path.pop()
            used[i] = False
    backtrack()
    return result

Time: O(n·n!). The base case triggers only at leaves, unlike Subsets where you collect at every level.

3. Combination Sum (LC 39): Reuse Without Going Backward

Difficulty: Medium.

Pass i instead of i + 1 when the same element can appear multiple times.

One character from the Subsets template, but it opens a completely different solution space. You can pick 2 again after picking 2. You can't go back to candidates[0] after already choosing to start at candidates[1]. One pruning trick earns its keep here: sort the candidates, then break when the current candidate exceeds the remaining target. Everything after it is larger and also impossible.

def combinationSum(candidates, target):
    result, path = [], []
    candidates.sort()
    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])   # i, not i+1
            path.pop()
    backtrack(0, target)
    return result

Time: O(n^(T/min)) where T is the target and min is the smallest candidate.

4. Subsets II (LC 90): The Duplicate Guard

Difficulty: Medium.

Sort first. Skip any element equal to its predecessor at the same recursion level.

This two-line pattern reappears unchanged in Combination Sum II (LC 40) and Permutations II (LC 47), so memorize it now. The condition is i > start, not i > 0. This is not a stylistic choice. Using i > 0 skips duplicates across different recursion levels, silently removing valid answers. Your code runs, produces results, looks almost right, and is wrong for specific inputs. That particular failure mode is fun to explain under time pressure.

def subsetsWithDup(nums):
    result, path = [], []
    nums.sort()
    def backtrack(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]: continue   # same-level skip only
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()
    backtrack(0)
    return result

Burn i > start into memory. It is not i > 0.

5. Letter Combinations of a Phone Number (LC 17): Mapping as Input

Difficulty: Medium.

When the input describes choices indirectly, backtrack over the lookup table.

The digits aren't chosen from a pool. They're fixed positions in the output. At each digit, you loop over its mapped letters, not over the remaining digits. This pattern shows up in interviews as "enumerate all expansions of this abbreviated string" or "generate all valid format variants." Same structure every time.

def letterCombinations(digits):
    if not digits: return []
    phone = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
             '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    result = []
    def backtrack(index, path):
        if index == len(digits):
            result.append("".join(path))
            return
        for char in phone[digits[index]]:
            path.append(char)
            backtrack(index + 1, path)
            path.pop()
    backtrack(0, [])
    return result

Time: O(4^n · n) worst case when all digits map to four letters.

6. Generate Parentheses (LC 22): Prune Before Recursing

Difficulty: Medium.

This problem shows what backtracking looks like when you can enforce validity at every step, not just at the leaves.

Two choices per position: ( or ). Two rules cut most of the tree immediately. You can't close a bracket if opens don't exceed closes. You can't open once you've placed all n. Enforcing both before each recursive call shrinks the search space from 2^(2n) to the nth Catalan number. For n=8, that's 1,430 valid strings instead of 65,536 possibilities. Pruning is not optional. It's the whole point.

def generateParenthesis(n):
    result = []
    def backtrack(path, opens, closes):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        if opens < n:
            path.append('(')
            backtrack(path, opens + 1, closes)
            path.pop()
        if closes < opens:
            path.append(')')
            backtrack(path, opens, closes + 1)
            path.pop()
    backtrack([], 0, 0)
    return result

If you want practice narrating this kind of constraint logic under time pressure, SpaceComplexity runs voice-based mock interviews that score that specific communication skill in real time.

7. Palindrome Partitioning (LC 131): Validate Before Descending

Difficulty: Medium.

Check whether a choice is valid before recursing on it, not after you reach the leaf.

Most people recurse first and validate at the bottom. That works, but it follows every path to completion before discovering it was dead. Palindrome Partitioning rewards a better habit: check each prefix before descending. If the substring isn't a palindrome, skip it entirely. Cheap O(n) check now beats expensive full-tree traversal later. This is the instinct that separates average-speed from fast-speed backtracking.

def partition(s):
    result, path = [], []
    def is_palindrome(t): return t == t[::-1]
    def backtrack(start):
        if start == len(s):
            result.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            sub = s[start:end]
            if is_palindrome(sub):
                path.append(sub)
                backtrack(end)
                path.pop()
    backtrack(0)
    return result

Time: O(n·2^n). An O(n^2) DP precomputation of all palindrome windows reduces each individual check from O(n) to O(1), which matters for long strings.

8. Word Search (LC 79): Grid State Without Extra Space

Difficulty: Medium.

In grid backtracking, mark cells in-place and restore them on return. The cell is its own visited flag.

An O(m·n) visited array works. The cleaner approach overwrites each cell with a sentinel (#) before recursing, then restores it after. One boolean grid replaced by two lines of mutation. The cell is borrowed, used, and returned. This trick reappears in LC 200 and most grid DFS problems worth knowing, so internalize it here.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(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
        tmp, board[r][c] = board[r][c], '#'
        found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1) or
                 dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1))
        board[r][c] = tmp
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

Time: O(m·n·4^L) where L is the word length.

9. N-Queens (LC 51): Three Constraint Sets in Parallel

Difficulty: Hard.

The actual insight is not the diagonal math. It's maintaining three independent constraints in O(1) per cell and keeping all three synchronized through the recursion.

Place one queen per row. Before placing in column c at row r, check three sets: columns already used, / diagonals blocked (row - col is constant along them), and \ anti-diagonals blocked (row + col is constant). All three are O(1) set lookups. Then add to all three before the recursive call. Remove from all three after. Miss a removal on any of the three and you get a subtly wrong answer that passes simple test cases and fails edge cases.

If you've ever come back to debug an N-Queens attempt and found that one diagonal set wasn't being restored, you are in good company.

def solveNQueens(n):
    result = []
    cols, diags, anti = set(), set(), set()
    board = [['.'] * n for _ in range(n)]
    def backtrack(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 diags or (row+col) in anti:
                continue
            cols.add(col); diags.add(row-col); anti.add(row+col)
            board[row][col] = 'Q'
            backtrack(row + 1)
            board[row][col] = '.'
            cols.remove(col); diags.remove(row-col); anti.remove(row+col)
    backtrack(0)
    return result

10. Word Search II (LC 212): A Trie as a Pruning Oracle

Difficulty: Hard.

When naive backtracking repeats work across multiple inputs, precompute a trie and let it decide when to stop.

Running LC 79 separately for each word in a dictionary costs O(W·m·n·4^L). The fix: build a trie from all words first, then run one DFS across the entire board. At each cell you descend into the trie alongside the grid. If the current path doesn't match any prefix in the dictionary, stop immediately. The trie kills entire branches that can't possibly complete any word, across all words, in a single pass.

This is the boss fight. Getting here means the template is solid. Now the question is whether you reach for the right precomputed structure when brute force becomes obviously too slow.

def findWords(board, words):
    from collections import defaultdict
    TrieNode = lambda: defaultdict(TrieNode)
    trie = TrieNode()
    for word in words:
        node = trie
        for ch in word:
            node = node[ch]
        node['#'] = word

    rows, cols = len(board), len(board[0])
    result = []

    def dfs(node, r, c):
        if '#' in node:
            result.append(node.pop('#'))      # pop prevents duplicates
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] not in node:
            return
        ch = board[r][c]
        board[r][c] = '#'
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(node[ch], r+dr, c+dc)
        board[r][c] = ch

    for r in range(rows):
        for c in range(cols):
            dfs(trie, r, c)
    return result

Time: O(m·n·4^L) worst case, but the trie exits most branches long before depth L.

What These Problems Actually Cover

Every structural variant that shows up in real interviews lives somewhere in this list:

Pure enumeration: Subsets, Permutations, Combination Sum
Duplicate handling: Subsets II (the i > start guard, not i > 0)
Mapped choices: Letter Combinations
Constraint-guided pruning: Generate Parentheses, N-Queens
Prefix validation before recursing: Palindrome Partitioning
In-place grid traversal: Word Search
Precomputed structure as pruning oracle: Word Search II

The pattern across all ten is identical: make a choice, recurse, undo. The only things that vary are which choices are available and which constraint decides validity. Once that clicks, an unfamiliar backtracking problem stops being a blank stare situation. It becomes "which variant is this?" and then you write the appropriate skeleton.

To identify which variant you're looking at before touching the keyboard, see how to spot a backtracking problem and the backtracking algorithm template. If complexity is the gap, the derivations live in backtracking time complexity.

One Template, Every Variation

1. Subsets (LC 78): Every Node Is an Answer

2. Permutations (LC 46): When Order Changes the Loop

3. Combination Sum (LC 39): Reuse Without Going Backward

4. Subsets II (LC 90): The Duplicate Guard

5. Letter Combinations of a Phone Number (LC 17): Mapping as Input

6. Generate Parentheses (LC 22): Prune Before Recursing

7. Palindrome Partitioning (LC 131): Validate Before Descending

8. Word Search (LC 79): Grid State Without Extra Space

9. N-Queens (LC 51): Three Constraint Sets in Parallel

10. Word Search II (LC 212): A Trie as a Pruning Oracle

What These Problems Actually Cover

Further Reading