LeetCode Patterns ·

🎯 Backtracking

1️⃣ Core Framework

When discussing Backtracking, I frame it as:

What problem pattern it solves
Decision tree thinking
Choose, explore, unchoose
Subsets
Combinations
Permutations
Combination Sum
N-Queens
Pruning
Senior-level explanation

2️⃣ What Problem Are We Solving?

Backtracking is used when we need to explore all possible choices.

It is commonly used for:

Subsets
Combinations
Permutations
Combination Sum
N-Queens
Sudoku Solver
Word Search
Palindrome Partitioning
Generate Parentheses
Constraint satisfaction problems

The core idea is:

Try one choice.
Explore deeper.
Undo the choice.
Try the next choice.

👉 Interview Answer

Backtracking is a DFS-based technique for exploring a decision tree.

At each step, we make a choice, recursively explore the result of that choice, and then undo the choice before trying another option.

It is useful when the problem requires generating all valid solutions or searching through combinations under constraints.

3️⃣ Why Backtracking Works

Decision Tree

Backtracking problems can often be modeled as a decision tree.

Example: choosing subsets from [1, 2, 3].

                 []
          /              \
       choose 1        skip 1
      /       \        /      \
 choose 2  skip 2  choose 2  skip 2

Each path from root to leaf represents one possible solution.

Core Pattern

choose
explore
unchoose

This means:

path.append(choice)
backtrack(...)
path.pop()

Why Undo Is Important

The same path object is reused across recursive calls.

After exploring one branch, we must undo the choice before exploring the next branch.

👉 Interview Answer

Backtracking works by exploring the decision tree of possible choices.

Each recursive call represents a partial solution.

We add one choice, recurse deeper, and then remove that choice to restore the previous state.

This allows us to systematically explore all valid possibilities.

4️⃣ Basic Backtracking Template

Template

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])
        return

    for choice in choices:
        if not is_valid(choice):
            continue

        path.append(choice)
        backtrack(path, next_choices)
        path.pop()

Key Components

Every backtracking problem usually needs:

Current path
Result list
Choices
Base case
Validity check
Recursive call
Undo step

👉 Interview Answer

A standard backtracking solution maintains a current path and explores available choices.

If the current path forms a complete solution, I copy it into the result.

Otherwise, I try each valid choice, recurse, and then undo the choice.

The undo step is what allows the same path object to be reused safely.

5️⃣ Backtracking vs DFS

DFS

DFS is a general traversal strategy.

It explores:

nodes, paths, graph branches, tree branches

Backtracking

Backtracking is DFS over a decision tree.

It explores:

choices
candidate solutions
constraint-based branches

Key Difference

DFS may only traverse.

Backtracking usually modifies state and then restores it.

choose → explore → unchoose

👉 Interview Answer

Backtracking is a specialized form of DFS.

DFS is the general idea of exploring deeply first.

Backtracking applies DFS to a decision tree where each recursive call represents a choice.

The key difference is that backtracking usually modifies state and then undoes that modification after recursion.

6️⃣ Subsets

Problem

Given a list of unique numbers, return all subsets.

nums = [1, 2, 3]

answer =
[
  [],
  [1],
  [2],
  [3],
  [1, 2],
  [1, 3],
  [2, 3],
  [1, 2, 3]
]

Code

def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])

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

    backtrack(0)
    return result

Key Insight

At every recursive call, the current path is already a valid subset.

So we add it to result before exploring deeper.

👉 Interview Answer

For subsets, every partial path is a valid answer.

I use a start index to avoid reusing previous elements.

At each call, I add a copy of the current path to the result.

Then I try adding each later element and recurse.

7️⃣ Subsets With Duplicates

Problem

Given nums that may contain duplicates, return all unique subsets.

nums = [1, 2, 2]

Key Idea

Sort first.

Then skip duplicate choices at the same recursion level.

Code

def subsets_with_dup(nums):
    nums.sort()
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])

        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue

            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Why `i > start`

This means:

Only skip duplicates at the same recursion level.

We still allow duplicate values to be used if they come from different levels.

👉 Interview Answer

For subsets with duplicates, I sort the array first.

Then, during the loop, if the current value is the same as the previous value at the same recursion level, I skip it.

This prevents generating duplicate subsets while still allowing valid repeated values in deeper levels.

8️⃣ Combinations

Problem

Choose k numbers from 1 to n.

n = 4, k = 2

answer =
[
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 3],
  [2, 4],
  [3, 4]
]

Code

def combine(n, k):
    result = []
    path = []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return

        for num in range(start, n + 1):
            path.append(num)
            backtrack(num + 1)
            path.pop()

    backtrack(1)
    return result

Key Insight

Use start to ensure numbers are selected in increasing order.

This prevents duplicate combinations like:

[1, 2]
[2, 1]

👉 Interview Answer

For combinations, I use a start index to enforce increasing order.

This ensures each combination is generated once.

When the path length reaches k, I copy the path into the result.

9️⃣ Combination Pruning

Why Pruning Helps

If we need k numbers but not enough numbers remain, there is no need to continue.

Optimized Loop

for num in range(start, n - remaining + 2):

Where:

remaining = k - len(path)

Code

def combine_optimized(n, k):
    result = []
    path = []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return

        remaining = k - len(path)

        for num in range(start, n - remaining + 2):
            path.append(num)
            backtrack(num + 1)
            path.pop()

    backtrack(1)
    return result

👉 Interview Answer

In combination problems, I can prune branches when there are not enough remaining numbers to complete the path.

If I still need remaining numbers, the loop does not need to go beyond n - remaining + 1.

This avoids exploring branches that cannot possibly form a valid combination.

🔟 Permutations

Problem

Return all permutations of unique numbers.

nums = [1, 2, 3]

answer =
[
  [1, 2, 3],
  [1, 3, 2],
  [2, 1, 3],
  [2, 3, 1],
  [3, 1, 2],
  [3, 2, 1]
]

Code

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

Key Insight

Unlike combinations, permutations care about order.

So every unused number is a valid next choice.

👉 Interview Answer

For permutations, order matters.

I use a used array to track which elements are already in the current path.

At each position, I try every unused number.

When the path length equals the input length, I add a copy to the result.

1️⃣1️⃣ Permutations With Duplicates

Problem

Return all unique permutations when nums may contain duplicates.

nums = [1, 1, 2]

Key Idea

Sort first.

Skip duplicate numbers if the previous identical number has not been used in this branch.

Code

def permute_unique(nums):
    nums.sort()
    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

            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(nums[i])

            backtrack()

            path.pop()
            used[i] = False

    backtrack()
    return result

Why This Skip Works

For duplicate values:

Only allow using the later duplicate after the earlier duplicate has been used.

This enforces a consistent order among equal values.

👉 Interview Answer

For unique permutations with duplicates, I sort nums first.

Then I skip nums[i] if it equals nums[i - 1] and the previous duplicate has not been used in the current branch.

This prevents generating the same permutation multiple times.

1️⃣2️⃣ Combination Sum

Problem

Given candidate numbers and target, return all combinations where numbers sum to target.

Each number can be used unlimited times.

Code

def combination_sum(candidates, target):
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return result

Why `backtrack(i, ...)`

Because the same number can be reused.

If each number could only be used once, we would call:

backtrack(i + 1, ...)

👉 Interview Answer

For Combination Sum, I use backtracking with a start index and remaining target.

If remaining becomes zero, I found a valid combination.

If remaining becomes negative, I stop that branch.

Since candidates can be reused, the recursive call uses the same index i.

1️⃣3️⃣ Combination Sum II

Problem

Each candidate can be used only once, and input may contain duplicates.

Code

def combination_sum2(candidates, target):
    candidates.sort()
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            if candidates[i] > remaining:
                break

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

    backtrack(0, target)
    return result

Key Differences From Combination Sum I

Use i + 1 because each number can be used once.
Sort and skip duplicates at same recursion level.
Break early if candidate > remaining.

👉 Interview Answer

Combination Sum II differs because each candidate can be used only once and duplicates may exist.

I sort the candidates first.

I skip duplicate values at the same recursion level.

Since each number can be used once, I recurse with i + 1.

If the current candidate is greater than remaining, I break early.

1️⃣4️⃣ Generate Parentheses

Problem

Generate all valid parentheses combinations with n pairs.

n = 3

answer =
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Key Rules

We can add "(" if:

open_count < n

We can add ")" if:

close_count < open_count

Code

def generate_parenthesis(n):
    result = []
    path = []

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

        if open_count < n:
            path.append("(")
            backtrack(open_count + 1, close_count)
            path.pop()

        if close_count < open_count:
            path.append(")")
            backtrack(open_count, close_count + 1)
            path.pop()

    backtrack(0, 0)
    return result

👉 Interview Answer

For Generate Parentheses, I build the string one character at a time.

I can add an opening parenthesis if I have used fewer than n opening parentheses.

I can add a closing parenthesis only if it would not make the string invalid, meaning close_count must be less than open_count.

When the path length reaches 2n, I add it to the result.

1️⃣5️⃣ Palindrome Partitioning

Problem

Partition a string so every substring is a palindrome.

s = "aab"

answer =
[
  ["a", "a", "b"],
  ["aa", "b"]
]

Code

def partition(s):
    result = []
    path = []

    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False

            left += 1
            right -= 1

        return True

    def backtrack(start):
        if start == len(s):
            result.append(path[:])
            return

        for end in range(start, len(s)):
            if not is_palindrome(start, end):
                continue

            path.append(s[start:end + 1])
            backtrack(end + 1)
            path.pop()

    backtrack(0)
    return result

Key Insight

Each recursive level chooses the next palindrome substring.

start = where the next substring begins
end = where the next substring ends

👉 Interview Answer

Palindrome Partitioning is a backtracking problem over string split positions.

At each step, I choose a substring starting at the current index.

If that substring is a palindrome, I add it to the path and recurse from the next index.

When start reaches the end of the string, the current path is a valid partition.

1️⃣6️⃣ Word Search

Problem

Given a board and a word, determine whether the word exists in the grid.

The word can be formed by adjacent cells, and each cell can be used only once.

Code

def exist(board, word):
    rows = len(board)
    cols = len(board[0])

    def dfs(r, c, index):
        if index == len(word):
            return True

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False

        if board[r][c] != word[index]:
            return False

        temp = board[r][c]
        board[r][c] = "#"

        found = (
            dfs(r + 1, c, index + 1)
            or dfs(r - 1, c, index + 1)
            or dfs(r, c + 1, index + 1)
            or dfs(r, c - 1, index + 1)
        )

        board[r][c] = temp

        return found

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

    return False

Why This Is Backtracking

We temporarily mark a cell as visited:

choose cell
explore neighbors
restore cell

👉 Interview Answer

Word Search is a grid DFS with backtracking.

Each recursive call tries to match the next character of the word.

I temporarily mark the current cell as visited so it cannot be reused in the same path.

After exploring all directions, I restore the cell.

1️⃣7️⃣ N-Queens

Problem

Place n queens on an n x n board so that no two queens attack each other.

Constraints

Queens cannot share:

same column
same main diagonal
same anti-diagonal

For cell (row, col):

main diagonal: row - col
anti diagonal: row + col

Code

def solve_n_queens(n):
    result = []
    board = [["."] * n for _ in range(n)]

    cols = set()
    diag1 = set()
    diag2 = set()

    def backtrack(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return

        for col in range(n):
            if col in cols:
                continue

            if row - col in diag1:
                continue

            if row + col in diag2:
                continue

            board[row][col] = "Q"
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            backtrack(row + 1)

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

    backtrack(0)
    return result

👉 Interview Answer

N-Queens is a classic constraint backtracking problem.

I place queens row by row.

For each position, I check whether the column and both diagonals are already occupied.

If the position is valid, I place the queen, recurse to the next row, and then remove the queen during backtracking.

1️⃣8️⃣ Sudoku Solver

Problem

Fill a 9x9 Sudoku board so each row, column, and 3x3 box contains digits 1 through 9.

Key Idea

Backtracking tries digits in empty cells.

If a digit is valid:

place it
recurse
if failed, undo it

Code

def solve_sudoku(board):
    def is_valid(r, c, ch):
        for i in range(9):
            if board[r][i] == ch:
                return False

            if board[i][c] == ch:
                return False

            box_row = 3 * (r // 3) + i // 3
            box_col = 3 * (c // 3) + i % 3

            if board[box_row][box_col] == ch:
                return False

        return True

    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    for ch in "123456789":
                        if is_valid(r, c, ch):
                            board[r][c] = ch

                            if backtrack():
                                return True

                            board[r][c] = "."

                    return False

        return True

    backtrack()

👉 Interview Answer

Sudoku Solver is a constraint satisfaction problem.

I scan for an empty cell.

For each digit from 1 to 9, I check whether placing it is valid for the row, column, and 3x3 box.

If valid, I place it and recurse.

If the recursion fails, I undo the placement and try the next digit.

1️⃣9️⃣ Pruning

What Is Pruning?

Pruning means stopping a branch early when it cannot lead to a valid solution.

Examples:

remaining sum < 0
candidate > remaining
path length already too large
invalid parentheses count
queen conflict
duplicate choice

Why It Matters

Backtracking can be exponential.

Pruning reduces the number of branches explored.

Example

In Combination Sum II:

if candidates[i] > remaining:
    break

This works because candidates are sorted.

👉 Interview Answer

Pruning is the process of cutting off branches that cannot produce a valid solution.

It is important because backtracking often explores an exponential search space.

Good pruning can greatly reduce runtime while preserving correctness.

2️⃣0️⃣ Handling Duplicates

Common Strategy

For duplicate inputs:

sort first
skip duplicate choices at the same recursion level

Common Pattern

if i > start and nums[i] == nums[i - 1]:
    continue

Used for:

subsets with duplicates
combination sum II

For Permutations

Use:

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

👉 Interview Answer

To handle duplicates in backtracking, I usually sort the input first.

For subset and combination problems, I skip duplicate values at the same recursion level.

For permutation problems, I use a used array and enforce a consistent ordering among equal values.

This prevents generating duplicate solutions.

2️⃣1️⃣ Complexity Analysis

Backtracking Complexity

Backtracking is often exponential.

Examples:

Subsets: O(2^n)
Permutations: O(n!)
Combinations: O(C(n, k))
N-Queens: roughly O(n!)

Space Complexity

Space includes:

recursion depth
current path
result output
visited or used sets

If excluding output:

usually O(n)

for recursion depth and path.

Important Note

If the result itself is huge, output size dominates.

👉 Interview Answer

Backtracking usually has exponential time complexity because it explores a decision tree.

For subsets, there are 2^n possible subsets.

For permutations, there are n! possible permutations.

Space complexity is usually O(n) excluding the output, but the output itself may also be exponential.

2️⃣2️⃣ Common Edge Cases

Empty Input

nums = []
s = ""
board = []

Single Element

nums = [1]

Duplicates

Need sorting and skip logic.

Target Already Reached

remaining == 0

Invalid Branch

remaining < 0
invalid choice
constraint violation

Mutable Path Copy

Must use:

path[:]

not:

path

👉 Interview Answer

Common backtracking edge cases include empty input, single element, duplicate values, target already reached, invalid branches, and copying the current path correctly.

Since path is mutable, I must append a copy of it to the result, not the path object itself.

2️⃣3️⃣ Common Mistakes

Mistake 1: Forgetting to Undo

Wrong:

path.append(x)
backtrack()

Missing:

path.pop()

Mistake 2: Appending Path Without Copy

Wrong:

result.append(path)

Correct:

result.append(path[:])

Mistake 3: Duplicate Handling Wrong

Skipping duplicates globally instead of only at the same recursion level.

Mistake 4: Wrong Start Index

Combination problems require:

backtrack(i + 1)

Reusable candidates require:

backtrack(i)

Mistake 5: No Pruning

Exploring branches that can never become valid.

Mistake 6: Confusing Permutations and Combinations

Permutations care about order.

Combinations do not.

👉 Interview Answer

Common backtracking mistakes include forgetting to undo choices, appending the mutable path without copying, handling duplicates incorrectly, using the wrong start index, missing pruning opportunities, and confusing permutations with combinations.

I avoid these by clearly defining what one recursion level represents.

2️⃣4️⃣ When Backtracking Applies

Good Fit

Use backtracking when the problem asks for:

all solutions
all combinations
all permutations
all subsets
valid configurations
constraint satisfaction
generate possible strings
search with undo

Problem Signals

Look for words like:

all
generate
find all
valid combinations
permutations
subsets
partition
place
arrange
constraint
can use once
can reuse

👉 Interview Answer

I consider backtracking when the problem asks to generate all valid solutions, explore combinations or permutations, or solve a constraint satisfaction problem.

The key signal is that we need to make choices recursively and undo them when exploring other branches.

2️⃣5️⃣ When Backtracking Does Not Apply

Not Good Fit

Backtracking may not be ideal when:

only need shortest path
need optimal value with overlapping subproblems
can solve greedily
need simple counting with formula
input size too large for exponential search

Better Alternatives

Problem Type	Better Pattern
Shortest path unweighted	BFS
Weighted shortest path	Dijkstra
Optimization with overlapping subproblems	Dynamic Programming
Local optimal choice works	Greedy
Need fast range query	Prefix Sum / Segment Tree
Need connectivity only	DFS / Union Find

👉 Interview Answer

Backtracking is powerful but often exponential.

If the problem only asks for shortest path, BFS may be better.

If the problem has overlapping subproblems and asks for an optimal value, dynamic programming may be better.

If the input size is large, pure backtracking may be too slow unless strong pruning exists.

2️⃣6️⃣ Standard Templates

General Backtracking Template

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])
        return

    for choice in choices:
        if not is_valid(choice):
            continue

        path.append(choice)
        backtrack(path, next_choices)
        path.pop()

Subsets Template

def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])

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

    backtrack(0)
    return result

Combinations Template

def combine(n, k):
    result = []
    path = []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return

        for num in range(start, n + 1):
            path.append(num)
            backtrack(num + 1)
            path.pop()

    backtrack(1)
    return result

Permutations Template

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

Combination Sum Template

def combination_sum(candidates, target):
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return result

Grid Backtracking Template

def search(board, word):
    rows = len(board)
    cols = len(board[0])

    def dfs(r, c, index):
        if index == len(word):
            return True

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False

        if board[r][c] != word[index]:
            return False

        temp = board[r][c]
        board[r][c] = "#"

        found = (
            dfs(r + 1, c, index + 1)
            or dfs(r - 1, c, index + 1)
            or dfs(r, c + 1, index + 1)
            or dfs(r, c - 1, index + 1)
        )

        board[r][c] = temp

        return found

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

    return False

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Backtracking is a DFS-based technique used to explore a decision tree of possible choices.

At each recursive call, we maintain a partial solution.

We choose one option, recursively explore deeper, and then undo the choice before trying the next option.

This is why the core pattern is choose, explore, unchoose.

Backtracking is commonly used for subsets, combinations, permutations, combination sum, generate parentheses, palindrome partitioning, word search, N-Queens, Sudoku, and other constraint satisfaction problems.

The most important design question is: what does one recursion level represent?

For subsets and combinations, one recursion level usually represents choosing the next element from a start index. The start index prevents reusing earlier elements and avoids duplicate orders.

For permutations, order matters, so we usually use a used array to track which elements are already in the path.

For combination sum, the recursive call uses the same index if candidates can be reused, and uses i + 1 if each candidate can only be used once.

Duplicate handling is a common issue. I usually sort the input first. For subsets and combinations, I skip duplicates at the same recursion level. For permutations, I use a used array and enforce a consistent order among equal values.

Pruning is critical because backtracking often explores an exponential search space. If a branch cannot possibly lead to a valid solution, such as remaining sum being negative, candidate greater than remaining, invalid parentheses count, or queen conflict, I stop that branch early.

The complexity depends on the size of the decision tree. Subsets are O(2^n), permutations are O(n!), combinations are O(C(n, k)), and many constraint problems are exponential in the worst case.

Space complexity is usually O(n) excluding output, due to recursion depth and the current path. The output itself may also be exponential.

At a senior level, I would explain: what the state is, what choices are available, what the base case is, how invalid branches are pruned, how duplicates are handled, and how the algorithm restores state after each recursive call.

⭐ Final Insight

Backtracking 的核心不是“暴力递归”。

它的核心是系统性地搜索 decision tree。

Senior-level 的重点是：

当前 state 是什么，每一层 recursion 代表什么 choice， base case 是什么，如何 prune invalid branches，如何 handle duplicates，以及为什么必须 choose、explore、unchoose。

能讲清楚这些， Backtracking 就是一种解决组合生成、排列搜索和约束满足问题的通用搜索模型。

中文部分

🎯 Backtracking

1️⃣ 核心框架

讨论 Backtracking 时，我通常从：

它解决什么问题
Decision tree 思维
Choose, explore, unchoose
Subsets
Combinations
Permutations
Combination Sum
N-Queens
Pruning
高级工程师解释方式

2️⃣ 要解决什么问题？

Backtracking 用于探索所有可能选择。

它常用于：

Subsets
Combinations
Permutations
Combination Sum
N-Queens
Sudoku Solver
Word Search
Palindrome Partitioning
Generate Parentheses
Constraint satisfaction problems

核心思想是：

尝试一个选择。
向下探索。
撤销这个选择。
再尝试下一个选择。

👉 面试回答

Backtracking 是一种基于 DFS 的搜索技巧。

它用于探索一个 decision tree。

在每一步，我们做出一个选择，递归探索这个选择带来的结果，然后撤销这个选择，再尝试其他选择。

它适合生成所有 valid solutions，或者在 constraints 下搜索所有可能配置。

3️⃣ 为什么 Backtracking 有效？

Decision Tree

Backtracking 问题通常可以建模成 decision tree。

Example：从 [1, 2, 3] 中选择 subsets。

                 []
          /              \
       choose 1        skip 1
      /       \        /      \
 choose 2  skip 2  choose 2  skip 2

从 root 到 leaf 的每条 path，都代表一种可能 solution。

Core Pattern

choose
explore
unchoose

也就是：

path.append(choice)
backtrack(...)
path.pop()

为什么需要 Undo？

因为同一个 path object 会在递归中反复使用。

探索完一个 branch 后，必须撤销当前 choice，再探索下一个 branch。

👉 面试回答

Backtracking 有效，是因为它系统性地探索所有 choices 构成的 decision tree。

每个 recursive call 代表一个 partial solution。

我们加入一个 choice，递归进入下一层，然后移除这个 choice，恢复之前的状态。

这样可以安全地探索所有可能分支。

4️⃣ Basic Backtracking Template

Template

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])
        return

    for choice in choices:
        if not is_valid(choice):
            continue

        path.append(choice)
        backtrack(path, next_choices)
        path.pop()

Key Components

每个 backtracking 通常需要：

Current path
Result list
Choices
Base case
Validity check
Recursive call
Undo step

👉 面试回答

标准 backtracking 维护一个 current path，并探索当前可选 choices。

如果当前 path 构成完整 solution，就把它的 copy 加入 result。

否则，尝试每一个 valid choice，递归向下探索，然后撤销这个 choice。

Undo step 是 backtracking 的关键。

5️⃣ Backtracking vs DFS

DFS

DFS 是通用 traversal strategy。

它探索：

nodes, paths, graph branches, tree branches

Backtracking

Backtracking 是 decision tree 上的 DFS。

它探索：

choices
candidate solutions
constraint-based branches

Key Difference

DFS 可能只是 traversal。

Backtracking 通常要修改 state，然后 restore state。

choose → explore → unchoose

👉 面试回答

Backtracking 是 DFS 的一种特殊形式。

DFS 是更通用的 deep exploration。

Backtracking 把 DFS 用在 decision tree 上，每个 recursive call 代表一次 choice。

最大区别是： backtracking 通常会修改当前 state，并在 recursion 返回后撤销这个修改。

6️⃣ Subsets

Problem

给定 unique numbers，返回所有 subsets。

nums = [1, 2, 3]

Code

def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])

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

    backtrack(0)
    return result

Key Insight

每一个 partial path 都是 valid subset。

所以进入 recursive call 时，当前 path 就可以加入 result。

👉 面试回答

对 subsets 来说，每个 partial path 都是一个 valid answer。

我用 start index 防止重复使用前面的元素。

在每个 recursive call 中，先把当前 path 的 copy 加入 result，然后继续尝试后面的元素。

7️⃣ Subsets With Duplicates

Problem

给定可能包含 duplicates 的 nums，返回所有 unique subsets。

nums = [1, 2, 2]

Key Idea

先 sort。

然后在同一 recursion level 跳过重复选择。

Code

def subsets_with_dup(nums):
    nums.sort()
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])

        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue

            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

为什么是 `i > start`

这表示：

只跳过同一层的 duplicate choices。

不同层仍然允许使用 duplicate value。

👉 面试回答

对 subsets with duplicates，我会先 sort nums。

然后在 for loop 中，如果当前值和前一个值相同，并且它们在同一 recursion level，就跳过当前值。

这样可以避免生成 duplicate subsets。

8️⃣ Combinations

Problem

从 1 到 n 中选择 k 个数。

n = 4, k = 2

Code

def combine(n, k):
    result = []
    path = []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return

        for num in range(start, n + 1):
            path.append(num)
            backtrack(num + 1)
            path.pop()

    backtrack(1)
    return result

Key Insight

使用 start 保证数字递增选择。

这样避免：

[1, 2]
[2, 1]

这种重复组合。

👉 面试回答

对 combinations，我用 start index 保证选择顺序递增。

这样每个 combination 只会生成一次。

当 path 长度等于 k 时，就把 path copy 到 result。

9️⃣ Combination Pruning

为什么 Pruning 有用？

如果需要 k 个数，但剩余数字已经不够了，就没有必要继续搜索。

Optimized Loop

for num in range(start, n - remaining + 2):

其中：

remaining = k - len(path)

Code

def combine_optimized(n, k):
    result = []
    path = []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return

        remaining = k - len(path)

        for num in range(start, n - remaining + 2):
            path.append(num)
            backtrack(num + 1)
            path.pop()

    backtrack(1)
    return result

👉 面试回答

在 combination 问题中，如果剩余数字数量已经不足以填满 path，就可以提前停止。

如果还需要 remaining 个数，那么 for loop 的最后起点不需要超过 n - remaining + 1。

这是一个简单但有效的 pruning。

🔟 Permutations

Problem

返回 unique numbers 的所有 permutations。

nums = [1, 2, 3]

Code

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

Key Insight

Permutation 关心 order。

所以每一层都可以从所有 unused numbers 里选一个。

👉 面试回答

对 permutations， order matters。

我用 used array 记录哪些元素已经在当前 path 中。

每一层递归都尝试所有还没使用过的数字。

当 path 长度等于 nums 长度时，就得到一个完整 permutation。

1️⃣1️⃣ Permutations With Duplicates

Problem

nums 可能包含 duplicates，返回所有 unique permutations。

nums = [1, 1, 2]

Key Idea

先 sort。

如果当前 duplicate 的前一个相同元素在本 branch 还没被使用，就跳过当前元素。

Code

def permute_unique(nums):
    nums.sort()
    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

            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(nums[i])

            backtrack()

            path.pop()
            used[i] = False

    backtrack()
    return result

为什么这样可以去重？

对于相同值：

只允许后面的 duplicate 在前一个 duplicate 已经被使用后再使用。

这强制 duplicate values 有固定相对顺序。

👉 面试回答

对 permutations with duplicates，我会先 sort nums。

然后如果 nums[i] 等于 nums[i - 1]，且前一个 duplicate 还没有在当前 branch 使用，就跳过 nums[i]。

这可以避免相同 permutation 被重复生成。

1️⃣2️⃣ Combination Sum

Problem

给定 candidates 和 target，返回所有 sum 等于 target 的 combinations。

每个 number 可以重复使用。

Code

def combination_sum(candidates, target):
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return result

为什么是 `backtrack(i, ...)`

因为当前 number 可以重复使用。

如果每个数只能用一次，则使用：

backtrack(i + 1, ...)

👉 面试回答

对 Combination Sum，我使用 start index 和 remaining target。

如果 remaining 变成 0，说明找到一个 valid combination。

如果 remaining 小于 0，当前 branch 无效。

因为 candidates 可以重复使用，所以 recursive call 继续从 i 开始。

1️⃣3️⃣ Combination Sum II

Problem

每个 candidate 只能用一次，并且 input 可能包含 duplicates。

Code

def combination_sum2(candidates, target):
    candidates.sort()
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            if candidates[i] > remaining:
                break

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

    backtrack(0, target)
    return result

和 Combination Sum I 的区别

Use i + 1 because each number can be used once.
Sort and skip duplicates at same recursion level.
Break early if candidate > remaining.

👉 面试回答

Combination Sum II 中，每个 candidate 只能使用一次，并且 input 可能有 duplicates。

我先 sort candidates。

在同一 recursion level 跳过 duplicate values。

因为每个数只能用一次，所以递归时使用 i + 1。

如果当前 candidate 已经大于 remaining，可以直接 break。

1️⃣4️⃣ Generate Parentheses

Problem

生成 n 对 parentheses 的所有 valid combinations。

n = 3

Key Rules

可以加 "(" 如果：

open_count < n

可以加 ")" 如果：

close_count < open_count

Code

def generate_parenthesis(n):
    result = []
    path = []

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

        if open_count < n:
            path.append("(")
            backtrack(open_count + 1, close_count)
            path.pop()

        if close_count < open_count:
            path.append(")")
            backtrack(open_count, close_count + 1)
            path.pop()

    backtrack(0, 0)
    return result

👉 面试回答

对 Generate Parentheses，我每次构造一个 character。

如果 open_count 小于 n，可以添加 opening parenthesis。

如果 close_count 小于 open_count，可以添加 closing parenthesis。

这样可以保证中间状态永远 valid。

当 path 长度达到 2n 时，得到一个完整答案。

1️⃣5️⃣ Palindrome Partitioning

Problem

把字符串切分成若干 substring，要求每个 substring 都是 palindrome。

s = "aab"
answer = [["a", "a", "b"], ["aa", "b"]]

Code

def partition(s):
    result = []
    path = []

    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False

            left += 1
            right -= 1

        return True

    def backtrack(start):
        if start == len(s):
            result.append(path[:])
            return

        for end in range(start, len(s)):
            if not is_palindrome(start, end):
                continue

            path.append(s[start:end + 1])
            backtrack(end + 1)
            path.pop()

    backtrack(0)
    return result

Key Insight

每一层递归选择下一个 palindrome substring。

start = next substring starts here
end = next substring ends here

👉 面试回答

Palindrome Partitioning 是对 string split positions 的 backtracking。

每一步选择一个从 start 开始的 substring。

如果这个 substring 是 palindrome，就加入 path，然后从 end + 1 继续递归。

当 start 到达字符串末尾，当前 path 就是一种 valid partition。

1️⃣6️⃣ Word Search

Problem

给定 board 和 word，判断 word 是否存在于 grid 中。

Word 可以由相邻 cells 组成，但每个 cell 只能使用一次。

Code

def exist(board, word):
    rows = len(board)
    cols = len(board[0])

    def dfs(r, c, index):
        if index == len(word):
            return True

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False

        if board[r][c] != word[index]:
            return False

        temp = board[r][c]
        board[r][c] = "#"

        found = (
            dfs(r + 1, c, index + 1)
            or dfs(r - 1, c, index + 1)
            or dfs(r, c + 1, index + 1)
            or dfs(r, c - 1, index + 1)
        )

        board[r][c] = temp

        return found

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

    return False

为什么这是 Backtracking？

我们临时把 cell 标记为 visited：

choose cell
explore neighbors
restore cell

👉 面试回答

Word Search 是 grid DFS with backtracking。

每个 recursive call 尝试匹配 word 的下一个 character。

我临时把当前 cell 标记为 visited，防止同一条 path 中重复使用。

探索完四个方向后，再 restore 当前 cell。

1️⃣7️⃣ N-Queens

Problem

在 n x n board 上放 n 个 queens，要求任意两个 queens 不能互相攻击。

Constraints

Queens 不能共享：

same column
same main diagonal
same anti-diagonal

对于 cell (row, col)：

main diagonal: row - col
anti diagonal: row + col

Code

def solve_n_queens(n):
    result = []
    board = [["."] * n for _ in range(n)]

    cols = set()
    diag1 = set()
    diag2 = set()

    def backtrack(row):
        if row == n:
            result.append(["".join(r) for r in board])
            return

        for col in range(n):
            if col in cols:
                continue

            if row - col in diag1:
                continue

            if row + col in diag2:
                continue

            board[row][col] = "Q"
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            backtrack(row + 1)

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

    backtrack(0)
    return result

👉 面试回答

N-Queens 是经典 constraint backtracking。

我按 row 放 queen。

对每个 column，检查 column、main diagonal 和 anti-diagonal 是否冲突。

如果位置 valid，就放 queen，进入下一行。

Recursion 返回后，再移除 queen 和相关状态。

1️⃣8️⃣ Sudoku Solver

Problem

填充 9x9 Sudoku board，让每一行、每一列、每个 3x3 box 都包含 1 到 9。

Key Idea

Backtracking 尝试在 empty cell 中填数字。

如果数字 valid：

place it
recurse
if failed, undo it

Code

def solve_sudoku(board):
    def is_valid(r, c, ch):
        for i in range(9):
            if board[r][i] == ch:
                return False

            if board[i][c] == ch:
                return False

            box_row = 3 * (r // 3) + i // 3
            box_col = 3 * (c // 3) + i % 3

            if board[box_row][box_col] == ch:
                return False

        return True

    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    for ch in "123456789":
                        if is_valid(r, c, ch):
                            board[r][c] = ch

                            if backtrack():
                                return True

                            board[r][c] = "."

                    return False

        return True

    backtrack()

👉 面试回答

Sudoku Solver 是 constraint satisfaction 问题。

我找到一个 empty cell。

然后尝试 1 到 9。

对每个 digit，检查它是否满足 row、column 和 3x3 box constraints。

如果 valid，就填入并递归。

如果后续失败，就撤销这个 digit，尝试下一个。

1️⃣9️⃣ Pruning

什么是 Pruning？

Pruning 指的是提前停止不可能产生 valid solution 的 branch。

Examples:

remaining sum < 0
candidate > remaining
path length already too large
invalid parentheses count
queen conflict
duplicate choice

为什么重要？

Backtracking 往往是 exponential。

Pruning 可以减少搜索分支。

Example

Combination Sum II 中：

if candidates[i] > remaining:
    break

因为 candidates 已经 sorted。

👉 面试回答

Pruning 是提前剪掉不可能得到 valid solution 的 branch。

Backtracking 通常搜索空间很大，所以 pruning 对性能非常重要。

比如 remaining sum 已经小于 0，或者 candidate 已经大于 remaining，当前 branch 就可以停止。

2️⃣0️⃣ Handling Duplicates

Common Strategy

对于 duplicate inputs：

sort first
skip duplicate choices at the same recursion level

Common Pattern

if i > start and nums[i] == nums[i - 1]:
    continue

用于：

subsets with duplicates
combination sum II

For Permutations

使用：

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

👉 面试回答

Backtracking 中处理 duplicates，我通常会先 sort input。

对 subset 和 combination 问题，我在同一 recursion level 跳过 duplicate choices。

对 permutation 问题，我使用 used array，并让相同 value 按固定顺序使用。

这样可以避免重复结果。

2️⃣1️⃣ Complexity Analysis

Backtracking Complexity

Backtracking 通常是 exponential。

Examples:

Subsets: O(2^n)
Permutations: O(n!)
Combinations: O(C(n, k))
N-Queens: roughly O(n!)

Space Complexity

Space 包括：

recursion depth
current path
result output
visited or used sets

如果不算 output：

usually O(n)

Important Note

如果 result 本身很大， output size 会主导复杂度。

👉 面试回答

Backtracking 通常是 exponential time complexity，因为它在探索 decision tree。

Subsets 有 2^n 个可能结果。

Permutations 有 n! 个可能结果。

Space complexity 如果不算 output，通常是 O(n)，来自 recursion depth 和 current path。

但 output 本身可能也是 exponential。

2️⃣2️⃣ 常见 Edge Cases

Empty Input

nums = []
s = ""
board = []

Single Element

nums = [1]

Duplicates

需要 sort 和 skip logic。

Target Already Reached

remaining == 0

Invalid Branch

remaining < 0
invalid choice
constraint violation

Mutable Path Copy

必须使用：

path[:]

而不是：

path

👉 面试回答

Backtracking 常见 edge cases 包括 empty input、 single element、 duplicate values、 target already reached、 invalid branch、以及正确复制 current path。

因为 path 是 mutable object，所以加入 result 时必须 append path 的 copy。

2️⃣3️⃣ 常见错误

Mistake 1: 忘记 Undo

错误：

path.append(x)
backtrack()

缺少：

path.pop()

Mistake 2: 没有 Copy Path

错误：

result.append(path)

正确：

result.append(path[:])

Mistake 3: Duplicate Handling 错误

把 duplicate skip 写成全局 skip，而不是 same recursion level skip。

Mistake 4: Start Index 错误

Combination problems 通常：

backtrack(i + 1)

可重复使用 candidates 时：

backtrack(i)

Mistake 5: 没有 Pruning

继续搜索明显不可能 valid 的 branch。

Mistake 6: 混淆 Permutations 和 Combinations

Permutations 关心 order。

Combinations 不关心 order。

👉 面试回答

Backtracking 常见错误包括：忘记 undo choice、 append mutable path 而不是 copy、 duplicate handling 错误、 start index 错误、没有 pruning、以及混淆 permutations 和 combinations。

我通常先定义清楚：每一层 recursion 代表什么。

2️⃣4️⃣ 什么时候 Backtracking 适用？

Good Fit

当题目问：

all solutions
all combinations
all permutations
all subsets
valid configurations
constraint satisfaction
generate possible strings
search with undo

Problem Signals

看到这些词想到 backtracking：

all
generate
find all
valid combinations
permutations
subsets
partition
place
arrange
constraint
can use once
can reuse

👉 面试回答

当题目要求生成所有 valid solutions、所有 combinations、permutations、subsets，或者是 constraint satisfaction problem 时，我会考虑 backtracking。

关键特征是：需要递归做选择，并在探索其他 branch 前撤销选择。

2️⃣5️⃣ 什么时候 Backtracking 不适用？

Not Good Fit

Backtracking 可能不适合：

only need shortest path
need optimal value with overlapping subproblems
can solve greedily
need simple counting with formula
input size too large for exponential search

Better Alternatives

Problem Type	Better Pattern
Shortest path unweighted	BFS
Weighted shortest path	Dijkstra
Optimization with overlapping subproblems	Dynamic Programming
Local optimal choice works	Greedy
Need fast range query	Prefix Sum / Segment Tree
Need connectivity only	DFS / Union Find

👉 面试回答

Backtracking 很强，但通常是 exponential。

如果题目只问 shortest path， BFS 可能更合适。

如果题目有 overlapping subproblems，并且要求 optimal value， dynamic programming 可能更合适。

如果 input size 很大，纯 backtracking 通常不现实，除非有很强的 pruning。

2️⃣6️⃣ 标准模板

General Backtracking Template

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:])
        return

    for choice in choices:
        if not is_valid(choice):
            continue

        path.append(choice)
        backtrack(path, next_choices)
        path.pop()

Subsets Template

def subsets(nums):
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])

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

    backtrack(0)
    return result

Combinations Template

def combine(n, k):
    result = []
    path = []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return

        for num in range(start, n + 1):
            path.append(num)
            backtrack(num + 1)
            path.pop()

    backtrack(1)
    return result

Permutations Template

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

Combination Sum Template

def combination_sum(candidates, target):
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    return result

Grid Backtracking Template

def search(board, word):
    rows = len(board)
    cols = len(board[0])

    def dfs(r, c, index):
        if index == len(word):
            return True

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False

        if board[r][c] != word[index]:
            return False

        temp = board[r][c]
        board[r][c] = "#"

        found = (
            dfs(r + 1, c, index + 1)
            or dfs(r - 1, c, index + 1)
            or dfs(r, c + 1, index + 1)
            or dfs(r, c - 1, index + 1)
        )

        board[r][c] = temp

        return found

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

    return False

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Backtracking 是一种基于 DFS 的搜索技巧，用来探索所有 possible choices 组成的 decision tree。

在每个 recursive call 中，我们维护一个 partial solution。

然后选择一个 option，递归向下探索，最后撤销这个 choice，再尝试下一个 option。

所以 backtracking 的核心模式是： choose、explore、unchoose。

Backtracking 常用于 subsets、combinations、permutations、combination sum、generate parentheses、palindrome partitioning、word search、N-Queens、Sudoku，以及其他 constraint satisfaction problems。

最重要的设计问题是：每一层 recursion 代表什么？

对 subsets 和 combinations，每一层通常表示从 start index 之后选择下一个元素。 Start index 可以防止重复使用前面的元素，并避免不同顺序生成相同组合。

对 permutations， order matters，所以通常使用 used array 记录哪些元素已经在当前 path 中。

对 combination sum，如果 candidates 可以重复使用， recursive call 使用同一个 index。如果每个 candidate 只能用一次， recursive call 使用 i + 1。

Duplicate handling 是 backtracking 常见难点。我通常先 sort input。对 subsets 和 combinations，在同一 recursion level 跳过 duplicate values。对 permutations，使用 used array，并强制 equal values 按固定顺序使用。

Pruning 非常重要，因为 backtracking 通常搜索 exponential space。如果某个 branch 不可能产生 valid solution，比如 remaining sum 小于 0、 candidate 大于 remaining、 parentheses count invalid、 queen conflict，就应该提前停止。

Complexity 取决于 decision tree 的大小。 Subsets 是 O(2^n)， permutations 是 O(n!)， combinations 是 O(C(n, k))，很多 constraint problems 最坏情况下都是 exponential。

如果不计算 output， space complexity 通常是 O(n)，来自 recursion depth 和 current path。但 output 本身可能也是 exponential。

高级工程师解释 backtracking 时，我会讲清楚： state 是什么， choices 是什么， base case 是什么，如何 prune invalid branches，如何处理 duplicates，以及每次 recursive call 后如何 restore state。

⭐ Final Insight

Backtracking 的核心不是“递归暴力搜索”。

它的核心是系统性地搜索 decision tree。

Senior-level 的重点是：

当前 state 是什么，每一层 recursion 代表什么 choice， base case 是什么，如何 prune invalid branches，如何 handle duplicates，以及为什么必须 choose、explore、unchoose。

能讲清楚这些， Backtracking 就是一种解决组合生成、排列搜索和约束满足问题的通用搜索模型。

🎯 Backtracking

1️⃣ Core Framework

2️⃣ What Problem Are We Solving?

3️⃣ Why Backtracking Works

Decision Tree

Core Pattern

Why Undo Is Important

4️⃣ Basic Backtracking Template

Template

Key Components

5️⃣ Backtracking vs DFS

DFS

Backtracking

Key Difference

6️⃣ Subsets

Problem

Code

Key Insight

7️⃣ Subsets With Duplicates

Problem

Key Idea

Code

Why i > start

8️⃣ Combinations

Problem

Code

Key Insight

9️⃣ Combination Pruning

Why Pruning Helps

Optimized Loop

Code

🔟 Permutations

Problem

Code

Key Insight

1️⃣1️⃣ Permutations With Duplicates

Problem

Key Idea

Code

Why This Skip Works

1️⃣2️⃣ Combination Sum

Problem

Code

Why backtrack(i, ...)

1️⃣3️⃣ Combination Sum II

Problem

Code

Key Differences From Combination Sum I

1️⃣4️⃣ Generate Parentheses

Problem

Key Rules

Code

1️⃣5️⃣ Palindrome Partitioning

Problem

Code

Key Insight

1️⃣6️⃣ Word Search

Problem

Code

Why This Is Backtracking

1️⃣7️⃣ N-Queens

Problem

Constraints

Code

1️⃣8️⃣ Sudoku Solver

Problem

Key Idea

Code

1️⃣9️⃣ Pruning

What Is Pruning?

Why It Matters

Example

2️⃣0️⃣ Handling Duplicates

Common Strategy

Common Pattern

For Permutations

2️⃣1️⃣ Complexity Analysis

Backtracking Complexity

Space Complexity

Important Note

Why `i > start`

Why `backtrack(i, ...)`

为什么是 `i > start`