回溯 · Backtracking

一句话骨架：在决策树上做 DFS——「做选择 → 递归到下一层 → 撤销选择」三段式雷打不动。回溯的难点不是写代码，而是画清楚「这一层在选什么」。

通用模板

python

def backtrack(path, choices):
    if 满足结束条件:
        res.append(path[:])     # 拷贝！否则后续 pop 会破坏快照
        return
    for c in choices:
        if 不合法: continue
        path.append(c)          # 做选择
        backtrack(path, 新的选择列表)
        path.pop()              # 撤销

关卡 1 · 全排列

学习目标

掌握「used 数组 + path[:] 拷贝」两件事；分清排列（used）vs 组合（start）的本质差异。

#46全排列中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1

输入nums = [1,2,3]

输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2

输入nums = [0,1]

输出[[0,1],[1,0]]

示例 3

输入nums = [1]

输出[[1]]

约束

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
nums 中的所有整数互不相同

💡 思路：在决策树上 DFS。每一层选择一个「未被使用过」的数加入 path；递归到 len(path) == n 就把 path 拷贝进 res；回溯前 pop 并把 used 标记还原。「used 数组」是排列题与组合题最大的写法分水岭——排列允许任意顺序所以靠 used，组合靠 start 防顺序重复。

✅ 完整解法

时间 O(n · n!)，每个排列长度 n、共 n! 个 · 空间 O(n) 递归栈与 path / used，不计输出

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def permute(nums: list[int]) -> list[list[int]]: 2    n = len(nums) 3    res, path = [], [] 4    used = [False] * n 5  6    def backtrack(): 7        if len(path) == n: 8            res.append(path[:])      # 必须拷贝快照，否则后续 pop 会改写 9            return10        for i in range(n):11            if used[i]:12                continue13            used[i] = True14            path.append(nums[i])15            backtrack()16            path.pop()               # 撤销17            used[i] = False18 19    backtrack()20    return res

🐞 单步可视化

可视化运行：nums = [1, 2, 3]

代码L2

 1def permute(nums: list[int]) -> list[list[int]]: 2    n = len(nums) 3    res, path = [], [] 4    used = [False] * n 5  6    def backtrack(): 7        if len(path) == n: 8            res.append(path[:])      # 必须拷贝快照，否则后续 pop 会改写 9            return10        for i in range(n):11            if used[i]:12                continue13            used[i] = True14            path.append(nums[i])15            backtrack()16            path.pop()               # 撤销17            used[i] = False18 19    backtrack()20    return res

数据流初始化

[ ]◀

[1]

[1,2]

[1,2,3]

[1,3]

[1,3,2]

[2]

[2,1]

[2,1,3]

[2,3]

[2,3,1]

[3]

[3,1]

[3,1,2]

[3,2]

[3,2,1]

● 当前 ● 路径祖先 ✓ 已收集叶子 ○ 待探索

path[]

used[FFF]↑ 下标 0 1 2

res[]

1 / 163读取输入：n = 3

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

回溯模板的三步是？

res.append(path[:]) 中的 path[:] 是在做什么？

 1def permute(nums: list[int]) -> list[list[int]]: 2    n = len(nums) 3    res, path = [], [] 4    used = [False] * n 5  6    def backtrack(): 7        if len(path) == n: 8            res.append(path[:])      # 必须拷贝快照，否则后续 pop 会改写 9            return10        for i in range(n):11            if used[i]:12                continue13            used[i] = True14            path.append(nums[i])15            backtrack()16            path.pop()               # 撤销17            used[i] = False18 19    backtrack()20    return res

used = [False]*n 的作用是？

 1def permute(nums: list[int]) -> list[list[int]]: 2    n = len(nums) 3    res, path = [], [] 4    used = [False] * n 5  6    def backtrack(): 7        if len(path) == n: 8            res.append(path[:])      # 必须拷贝快照，否则后续 pop 会改写 9            return10        for i in range(n):11            if used[i]:12                continue13            used[i] = True14            path.append(nums[i])15            backtrack()16            path.pop()               # 撤销17            used[i] = False18 19    backtrack()20    return res

为什么排列题用 used，而组合题（如 LC39）用 start 参数？

回溯到 len(path) == n 时为什么要 return？

 1def permute(nums: list[int]) -> list[list[int]]: 2    n = len(nums) 3    res, path = [], [] 4    used = [False] * n 5  6    def backtrack(): 7        if len(path) == n: 8            res.append(path[:])      # 必须拷贝快照，否则后续 pop 会改写 9            return10        for i in range(n):11            if used[i]:12                continue13            used[i] = True14            path.append(nums[i])15            backtrack()16            path.pop()               # 撤销17            used[i] = False18 19    backtrack()20    return res

path.pop() 与 used[i] = False 的顺序是否必须严格？

 1def permute(nums: list[int]) -> list[list[int]]: 2    n = len(nums) 3    res, path = [], [] 4    used = [False] * n 5  6    def backtrack(): 7        if len(path) == n: 8            res.append(path[:])      # 必须拷贝快照，否则后续 pop 会改写 9            return10        for i in range(n):11            if used[i]:12                continue13            used[i] = True14            path.append(nums[i])15            backtrack()16            path.pop()               # 撤销17            used[i] = False18 19    backtrack()20    return res

为什么不写 path.append(nums[i]); used[i] = True; backtrack(); used[i] = False; path.pop()，把 used 移到第二步可不可以？

permute([1,2,3]) 共有多少种排列？

时间复杂度的「严格」表达是？

若数组里有重复（LC47），最常见的去重技巧是？

空间复杂度（不计输出 res）是？

如果用「在数组里 swap 两端」的写法（无 used、就地交换）相比 used 版的差别？

关卡 2 · 组合总和

学习目标

体会「start 参数防顺序重复」与「下一层从 i 开始 → 同元素可重选」两条招牌细节。

#39组合总和中等

♥♥♥♥♥+0 XP🔥 0

0 / 11

📝 题目

给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1

输入candidates = [2,3,6,7], target = 7

输出[[2,2,3],[7]]

示例 2

输入candidates = [2,3,5], target = 8

输出[[2,2,2,2],[2,3,3],[3,5]]

示例 3

输入candidates = [2], target = 1

输出[]

约束

1 ≤ candidates.length ≤ 30
2 ≤ candidates[i] ≤ 40
candidates 的所有元素互不相同
1 ≤ target ≤ 40

💡 思路：回溯 + start 参数防顺序重复。核心两点：① 用 `start` 参数（每层从 i 开始而非 i+1）允许同元素重复；② 排序 + `if x > remain: break` 把越往后越大的尾巴一刀切掉。如果不要求同元素重复，下一层应当是 i+1。

✅ 完整解法

时间 O(N^(T/M))，N 为 candidates 数、T 为 target、M 为最小值（决策树高度上界 T/M） · 空间 O(T/M) 递归栈与 path

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def combinationSum(candidates: list[int], target: int) -> list[list[int]]: 2    candidates.sort()                  # 排序后可以提前剪枝（剩余 target 不够时 break） 3    res, path = [], [] 4  5    def backtrack(start: int, remain: int) -> None: 6        if remain == 0: 7            res.append(path[:]) 8            return 9        for i in range(start, len(candidates)):10            x = candidates[i]11            if x > remain:             # 排序后越往后越大——直接 break 而非 continue12                break13            path.append(x)14            backtrack(i, remain - x)   # 注意是 i 而不是 i+1：同一个数允许重复使用15            path.pop()16 17    backtrack(0, target)18    return res

🐞 单步可视化

可视化运行：candidates = [2, 3, 6, 7], target = 7

代码L2

 1def combinationSum(candidates: list[int], target: int) -> list[list[int]]: 2    candidates.sort()                  # 排序后可以提前剪枝（剩余 target 不够时 break） 3    res, path = [], [] 4  5    def backtrack(start: int, remain: int) -> None: 6        if remain == 0: 7            res.append(path[:]) 8            return 9        for i in range(start, len(candidates)):10            x = candidates[i]11            if x > remain:             # 排序后越往后越大——直接 break 而非 continue12                break13            path.append(x)14            backtrack(i, remain - x)   # 注意是 i 而不是 i+1：同一个数允许重复使用15            path.pop()16 17    backtrack(0, target)18    return res

数据流初始化

[] sum=0◀

[2] sum=2

[2,2] sum=4

[2,2,2] sum=6

[2,2,2,2] sum=8✗

[2,2,2,3] sum=9✗

[2,2,2,6] sum=12✗

[2,2,2,7] sum=13✗

[2,2,3] sum=7

[2,2,6] sum=10✗

[2,2,7] sum=11✗

[2,3] sum=5

[2,3,3] sum=8✗

[2,3,6] sum=11✗

[2,3,7] sum=12✗

[2,6] sum=8✗

[2,7] sum=9✗

[3] sum=3

[3,3] sum=6

[3,3,3] sum=9✗

[3,3,6] sum=12✗

[3,3,7] sum=13✗

[3,6] sum=9✗

[3,7] sum=10✗

[6] sum=6

[6,6] sum=12✗

[6,7] sum=13✗

[7] sum=7

● 当前 ● 路径祖先 ✓ 已收集叶子 ○ 待探索

path[]

used[FFFF]↑ 下标 0 1 2 3

res[]

1 / 116读取输入：candidates = [2,3,6,7], target = 7

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么递归调用是 backtrack(i, ...) 而不是 backtrack(i+1, ...)？

 1def combinationSum(candidates: list[int], target: int) -> list[list[int]]: 2    candidates.sort()                  # 排序后可以提前剪枝（剩余 target 不够时 break） 3    res, path = [], [] 4  5    def backtrack(start: int, remain: int) -> None: 6        if remain == 0: 7            res.append(path[:]) 8            return 9        for i in range(start, len(candidates)):10            x = candidates[i]11            if x > remain:             # 排序后越往后越大——直接 break 而非 continue12                break13            path.append(x)14            backtrack(i, remain - x)   # 注意是 i 而不是 i+1：同一个数允许重复使用15            path.pop()16 17    backtrack(0, target)18    return res

为什么用 start 参数而不是 used 数组？

candidates.sort() + if x > remain: break 的剪枝意义？

 1def combinationSum(candidates: list[int], target: int) -> list[list[int]]: 2    candidates.sort()                  # 排序后可以提前剪枝（剩余 target 不够时 break） 3    res, path = [], [] 4  5    def backtrack(start: int, remain: int) -> None: 6        if remain == 0: 7            res.append(path[:]) 8            return 9        for i in range(start, len(candidates)):10            x = candidates[i]11            if x > remain:             # 排序后越往后越大——直接 break 而非 continue12                break13            path.append(x)14            backtrack(i, remain - x)   # 注意是 i 而不是 i+1：同一个数允许重复使用15            path.pop()16 17    backtrack(0, target)18    return res

终止条件应当是？

 1def combinationSum(candidates: list[int], target: int) -> list[list[int]]: 2    candidates.sort()                  # 排序后可以提前剪枝（剩余 target 不够时 break） 3    res, path = [], [] 4  5    def backtrack(start: int, remain: int) -> None: 6        if remain == 0: 7            res.append(path[:]) 8            return 9        for i in range(start, len(candidates)):10            x = candidates[i]11            if x > remain:             # 排序后越往后越大——直接 break 而非 continue12                break13            path.append(x)14            backtrack(i, remain - x)   # 注意是 i 而不是 i+1：同一个数允许重复使用15            path.pop()16 17    backtrack(0, target)18    return res

res.append(path[:]) 的核心意义？

 1def combinationSum(candidates: list[int], target: int) -> list[list[int]]: 2    candidates.sort()                  # 排序后可以提前剪枝（剩余 target 不够时 break） 3    res, path = [], [] 4  5    def backtrack(start: int, remain: int) -> None: 6        if remain == 0: 7            res.append(path[:]) 8            return 9        for i in range(start, len(candidates)):10            x = candidates[i]11            if x > remain:             # 排序后越往后越大——直接 break 而非 continue12                break13            path.append(x)14            backtrack(i, remain - x)   # 注意是 i 而不是 i+1：同一个数允许重复使用15            path.pop()16 17    backtrack(0, target)18    return res

for i in range(start, len(candidates)) 的 start 决定了什么？

 1def combinationSum(candidates: list[int], target: int) -> list[list[int]]: 2    candidates.sort()                  # 排序后可以提前剪枝（剩余 target 不够时 break） 3    res, path = [], [] 4  5    def backtrack(start: int, remain: int) -> None: 6        if remain == 0: 7            res.append(path[:]) 8            return 9        for i in range(start, len(candidates)):10            x = candidates[i]11            if x > remain:             # 排序后越往后越大——直接 break 而非 continue12                break13            path.append(x)14            backtrack(i, remain - x)   # 注意是 i 而不是 i+1：同一个数允许重复使用15            path.pop()16 17    backtrack(0, target)18    return res

若 candidates 中存在重复元素（即变成 LC40），需要做哪两点改动？

combinationSum([2,3,6,7], 7) 的两个解中，[2,2,3] 是怎么搜出来的？

本题的复杂度上界以哪个因素为主？

if x > remain: break 写成 continue 是否仍然正确？

 1def combinationSum(candidates: list[int], target: int) -> list[list[int]]: 2    candidates.sort()                  # 排序后可以提前剪枝（剩余 target 不够时 break） 3    res, path = [], [] 4  5    def backtrack(start: int, remain: int) -> None: 6        if remain == 0: 7            res.append(path[:]) 8            return 9        for i in range(start, len(candidates)):10            x = candidates[i]11            if x > remain:             # 排序后越往后越大——直接 break 而非 continue12                break13            path.append(x)14            backtrack(i, remain - x)   # 注意是 i 而不是 i+1：同一个数允许重复使用15            path.pop()16 17    backtrack(0, target)18    return res

空间复杂度（不计 res）是？

关卡 3 · N 皇后

学习目标

学会用三个 set（cols / row-col / row+col）把冲突检查从 O(n) 压到 O(1)。

#51N 皇后困难

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

N 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n，返回所有不同的 N 皇后问题的解决方案。每一种解法包含一个不同的 N 皇后问题的棋子放置方案，该方案中 Q 和 . 分别代表了皇后和空位。

示例 1

输入n = 4

输出[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

示例 2

输入n = 1

输出[["Q"]]

约束

1 ≤ n ≤ 9

💡 思路：按行枚举（同行天然不能再放）→ 每行选一列。三种冲突一次 O(1) 检查：① cols 记录列；② diag1 记录 row-col 主对角线；③ diag2 记录 row+col 副对角线。同一对角线上的格子 row-col（或 row+col）相等。

✅ 完整解法

时间 O(n!) — 第一行 n 种、第二行至多 n-2 种… · 空间 O(n) — 三个 set 各 ≤ n、递归栈 ≤ n

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def solveNQueens(n: int) -> list[list[str]]: 2    res = [] 3    cols = set()      # 已占的列 4    diag1 = set()     # 已占的「主对角线」：row - col 相同 5    diag2 = set()     # 已占的「副对角线」：row + col 相同 6    queens = [-1] * n # queens[row] = col 7  8    def backtrack(row: int) -> None: 9        if row == n:10            board = []11            for r in range(n):12                line = ['.'] * n13                line[queens[r]] = 'Q'14                board.append(''.join(line))15            res.append(board)16            return17        for col in range(n):18            if col in cols or (row - col) in diag1 or (row + col) in diag2:19                continue20            cols.add(col); diag1.add(row - col); diag2.add(row + col)21            queens[row] = col22            backtrack(row + 1)23            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)24 25    backtrack(0)26    return res

🐞 单步可视化

可视化运行：n = 4（4×4 棋盘）

代码L2

 1def solveNQueens(n: int) -> list[list[str]]: 2    res = [] 3    cols = set()      # 已占的列 4    diag1 = set()     # 已占的「主对角线」：row - col 相同 5    diag2 = set()     # 已占的「副对角线」：row + col 相同 6    queens = [-1] * n # queens[row] = col 7  8    def backtrack(row: int) -> None: 9        if row == n:10            board = []11            for r in range(n):12                line = ['.'] * n13                line[queens[r]] = 'Q'14                board.append(''.join(line))15            res.append(board)16            return17        for col in range(n):18            if col in cols or (row - col) in diag1 or (row + col) in diag2:19                continue20            cols.add(col); diag1.add(row - col); diag2.add(row + col)21            queens[row] = col22            backtrack(row + 1)23            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)24 25    backtrack(0)26    return res

数据流初始化

[ ]◀

[r0c0]

[r0c0,r1c0]✗

[r0c0,r1c1]✗

[r0c0,r1c2]

[r0c0,r1c2,r2c0]✗

[r0c0,r1c2,r2c1]✗

[r0c0,r1c2,r2c2]✗

[r0c0,r1c2,r2c3]✗

[r0c0,r1c3]

[r0c0,r1c3,r2c0]✗

[r0c0,r1c3,r2c1]

[r0c0,r1c3,r2c1,r3c0]✗

[r0c0,r1c3,r2c1,r3c1]✗

[r0c0,r1c3,r2c1,r3c2]✗

[r0c0,r1c3,r2c1,r3c3]✗

[r0c0,r1c3,r2c2]✗

[r0c0,r1c3,r2c3]✗

[r0c1]

[r0c1,r1c0]✗

[r0c1,r1c1]✗

[r0c1,r1c2]✗

[r0c1,r1c3]

[r0c1,r1c3,r2c0]

[r0c1,r1c3,r2c0,r3c0]✗

[r0c1,r1c3,r2c0,r3c1]✗

[r0c1,r1c3,r2c0,r3c2]

[r0c1,r1c3,r2c0,r3c3]✗

[r0c1,r1c3,r2c1]✗

[r0c1,r1c3,r2c2]✗

[r0c1,r1c3,r2c3]✗

[r0c2]

[r0c2,r1c0]

[r0c2,r1c0,r2c0]✗

[r0c2,r1c0,r2c1]✗

[r0c2,r1c0,r2c2]✗

[r0c2,r1c0,r2c3]

[r0c2,r1c0,r2c3,r3c0]✗

[r0c2,r1c0,r2c3,r3c1]

[r0c2,r1c0,r2c3,r3c2]✗

[r0c2,r1c0,r2c3,r3c3]✗

[r0c2,r1c1]✗

[r0c2,r1c2]✗

[r0c2,r1c3]✗

[r0c3]

[r0c3,r1c0]

[r0c3,r1c0,r2c0]✗

[r0c3,r1c0,r2c1]✗

[r0c3,r1c0,r2c2]

[r0c3,r1c0,r2c2,r3c0]✗

[r0c3,r1c0,r2c2,r3c1]✗

[r0c3,r1c0,r2c2,r3c2]✗

[r0c3,r1c0,r2c2,r3c3]✗

[r0c3,r1c0,r2c3]✗

[r0c3,r1c1]

[r0c3,r1c1,r2c0]✗

[r0c3,r1c1,r2c1]✗

[r0c3,r1c1,r2c2]✗

[r0c3,r1c1,r2c3]✗

[r0c3,r1c2]✗

[r0c3,r1c3]✗

● 当前 ● 路径祖先 ✓ 已收集叶子 ○ 待探索

path[]

used[FFFF]↑ 下标 0 1 2 3

res[]

1 / 236n = 4；目标：每行放一个皇后，列 / 主对角 / 副对角都不冲突

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么我们不需要「row 是否被占」的检查？

同一条「主对角线」（左上→右下）上格子的什么值相等？

 1def solveNQueens(n: int) -> list[list[str]]: 2    res = [] 3    cols = set()      # 已占的列 4    diag1 = set()     # 已占的「主对角线」：row - col 相同 5    diag2 = set()     # 已占的「副对角线」：row + col 相同 6    queens = [-1] * n # queens[row] = col 7  8    def backtrack(row: int) -> None: 9        if row == n:10            board = []11            for r in range(n):12                line = ['.'] * n13                line[queens[r]] = 'Q'14                board.append(''.join(line))15            res.append(board)16            return17        for col in range(n):18            if col in cols or (row - col) in diag1 or (row + col) in diag2:19                continue20            cols.add(col); diag1.add(row - col); diag2.add(row + col)21            queens[row] = col22            backtrack(row + 1)23            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)24 25    backtrack(0)26    return res

同一条「副对角线」（右上→左下）上格子的什么值相等？

 1def solveNQueens(n: int) -> list[list[str]]: 2    res = [] 3    cols = set()      # 已占的列 4    diag1 = set()     # 已占的「主对角线」：row - col 相同 5    diag2 = set()     # 已占的「副对角线」：row + col 相同 6    queens = [-1] * n # queens[row] = col 7  8    def backtrack(row: int) -> None: 9        if row == n:10            board = []11            for r in range(n):12                line = ['.'] * n13                line[queens[r]] = 'Q'14                board.append(''.join(line))15            res.append(board)16            return17        for col in range(n):18            if col in cols or (row - col) in diag1 or (row + col) in diag2:19                continue20            cols.add(col); diag1.add(row - col); diag2.add(row + col)21            queens[row] = col22            backtrack(row + 1)23            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)24 25    backtrack(0)26    return res

if col in cols or (row - col) in diag1 or (row + col) in diag2 这一行检查的是？

 1def solveNQueens(n: int) -> list[list[str]]: 2    res = [] 3    cols = set()      # 已占的列 4    diag1 = set()     # 已占的「主对角线」：row - col 相同 5    diag2 = set()     # 已占的「副对角线」：row + col 相同 6    queens = [-1] * n # queens[row] = col 7  8    def backtrack(row: int) -> None: 9        if row == n:10            board = []11            for r in range(n):12                line = ['.'] * n13                line[queens[r]] = 'Q'14                board.append(''.join(line))15            res.append(board)16            return17        for col in range(n):18            if col in cols or (row - col) in diag1 or (row + col) in diag2:19                continue20            cols.add(col); diag1.add(row - col); diag2.add(row + col)21            queens[row] = col22            backtrack(row + 1)23            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)24 25    backtrack(0)26    return res

为什么用三个 set 比「每次扫已放皇后逐个比对」快？

回溯撤销时为什么三个 set 都要 remove？

 1def solveNQueens(n: int) -> list[list[str]]: 2    res = [] 3    cols = set()      # 已占的列 4    diag1 = set()     # 已占的「主对角线」：row - col 相同 5    diag2 = set()     # 已占的「副对角线」：row + col 相同 6    queens = [-1] * n # queens[row] = col 7  8    def backtrack(row: int) -> None: 9        if row == n:10            board = []11            for r in range(n):12                line = ['.'] * n13                line[queens[r]] = 'Q'14                board.append(''.join(line))15            res.append(board)16            return17        for col in range(n):18            if col in cols or (row - col) in diag1 or (row + col) in diag2:19                continue20            cols.add(col); diag1.add(row - col); diag2.add(row + col)21            queens[row] = col22            backtrack(row + 1)23            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)24 25    backtrack(0)26    return res

queens = [-1]*n 的作用是？

 1def solveNQueens(n: int) -> list[list[str]]: 2    res = [] 3    cols = set()      # 已占的列 4    diag1 = set()     # 已占的「主对角线」：row - col 相同 5    diag2 = set()     # 已占的「副对角线」：row + col 相同 6    queens = [-1] * n # queens[row] = col 7  8    def backtrack(row: int) -> None: 9        if row == n:10            board = []11            for r in range(n):12                line = ['.'] * n13                line[queens[r]] = 'Q'14                board.append(''.join(line))15            res.append(board)16            return17        for col in range(n):18            if col in cols or (row - col) in diag1 or (row + col) in diag2:19                continue20            cols.add(col); diag1.add(row - col); diag2.add(row + col)21            queens[row] = col22            backtrack(row + 1)23            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)24 25    backtrack(0)26    return res

把字符串行 ["...Q"] 拼起来时常用的写法是？

 1def solveNQueens(n: int) -> list[list[str]]: 2    res = [] 3    cols = set()      # 已占的列 4    diag1 = set()     # 已占的「主对角线」：row - col 相同 5    diag2 = set()     # 已占的「副对角线」：row + col 相同 6    queens = [-1] * n # queens[row] = col 7  8    def backtrack(row: int) -> None: 9        if row == n:10            board = []11            for r in range(n):12                line = ['.'] * n13                line[queens[r]] = 'Q'14                board.append(''.join(line))15            res.append(board)16            return17        for col in range(n):18            if col in cols or (row - col) in diag1 or (row + col) in diag2:19                continue20            cols.add(col); diag1.add(row - col); diag2.add(row + col)21            queens[row] = col22            backtrack(row + 1)23            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)24 25    backtrack(0)26    return res

n=4 一共有几个解？

本题最坏时间复杂度的合理表达？

若题目改成「LC52 只问解的个数」，最易优化是？

空间复杂度（不计输出）是？

关卡 4 · 单词搜索

学习目标

掌握网格回溯三段式：「占位 board[i][j]='#' → 四方向递归 → 出 dfs 还原」。

#79单词搜索中等

♥♥♥♥♥+0 XP🔥 0

0 / 11

📝 题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中「相邻」单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1

输入

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"

输出true

示例 2

输入

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "SEE"

输出true

示例 3

输入

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCB"

输出false

约束

m == board.length, n == board[i].length
1 ≤ m, n ≤ 6
1 ≤ word.length ≤ 15
board 与 word 仅由大小写英文字母组成

💡 思路：从每个格子出发 DFS：当前字符等于 word[k] 才继续往四方向走，递归 word[k+1]。「占位 + 还原」模板：进 dfs 把 board[i][j] 改成 #、出 dfs 还原原字符——既能防止重复使用同格、又不需要额外 visited 数组。

✅ 完整解法

时间 O(m·n·4^L)，L 为 word 长度 · 空间 O(L) 递归栈

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def exist(board: list[list[str]], word: str) -> bool: 2    m, n = len(board), len(board[0]) 3  4    def dfs(i: int, j: int, k: int) -> bool: 5        if k == len(word): 6            return True 7        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: 8            return False 9        tmp = board[i][j]10        board[i][j] = '#'                # 占位，防止本路径再次走回来11        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1)12                 or dfs(i, j+1, k+1) or dfs(i, j-1, k+1))13        board[i][j] = tmp                # 回溯还原14        return found15 16    for i in range(m):17        for j in range(n):18            if dfs(i, j, 0):19                return True20    return False

🐞 单步可视化

示例：3×4 网格，word = "ABCCED"

代码L2

 1def exist(board: list[list[str]], word: str) -> bool: 2    m, n = len(board), len(board[0]) 3  4    def dfs(i: int, j: int, k: int) -> bool: 5        if k == len(word): 6            return True 7        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: 8            return False 9        tmp = board[i][j]10        board[i][j] = '#'                # 占位，防止本路径再次走回来11        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1)12                 or dfs(i, j+1, k+1) or dfs(i, j-1, k+1))13        board[i][j] = tmp                # 回溯还原14        return found15 16    for i in range(m):17        for j in range(n):18            if dfs(i, j, 0):19                return True20    return False

数据流

wordABCCEDk·foundfalse

1 / 51输入：3×4 网格，word = "ABCCED"

速度

🧠 理解检验

每题都对应解法的某一行或某个决策

从每个格子尝试一次 DFS，外层循环的目的？

 1def exist(board: list[list[str]], word: str) -> bool: 2    m, n = len(board), len(board[0]) 3  4    def dfs(i: int, j: int, k: int) -> bool: 5        if k == len(word): 6            return True 7        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: 8            return False 9        tmp = board[i][j]10        board[i][j] = '#'                # 占位，防止本路径再次走回来11        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1)12                 or dfs(i, j+1, k+1) or dfs(i, j-1, k+1))13        board[i][j] = tmp                # 回溯还原14        return found15 16    for i in range(m):17        for j in range(n):18            if dfs(i, j, 0):19                return True20    return False

board[i][j] = "#" 这一句的本质是？

 1def exist(board: list[list[str]], word: str) -> bool: 2    m, n = len(board), len(board[0]) 3  4    def dfs(i: int, j: int, k: int) -> bool: 5        if k == len(word): 6            return True 7        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: 8            return False 9        tmp = board[i][j]10        board[i][j] = '#'                # 占位，防止本路径再次走回来11        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1)12                 or dfs(i, j+1, k+1) or dfs(i, j-1, k+1))13        board[i][j] = tmp                # 回溯还原14        return found15 16    for i in range(m):17        for j in range(n):18            if dfs(i, j, 0):19                return True20    return False

为什么必须把 tmp = board[i][j] 提前保存？

 1def exist(board: list[list[str]], word: str) -> bool: 2    m, n = len(board), len(board[0]) 3  4    def dfs(i: int, j: int, k: int) -> bool: 5        if k == len(word): 6            return True 7        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: 8            return False 9        tmp = board[i][j]10        board[i][j] = '#'                # 占位，防止本路径再次走回来11        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1)12                 or dfs(i, j+1, k+1) or dfs(i, j-1, k+1))13        board[i][j] = tmp                # 回溯还原14        return found15 16    for i in range(m):17        for j in range(n):18            if dfs(i, j, 0):19                return True20    return False

if k == len(word): return True 这行作用？

 1def exist(board: list[list[str]], word: str) -> bool: 2    m, n = len(board), len(board[0]) 3  4    def dfs(i: int, j: int, k: int) -> bool: 5        if k == len(word): 6            return True 7        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: 8            return False 9        tmp = board[i][j]10        board[i][j] = '#'                # 占位，防止本路径再次走回来11        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1)12                 or dfs(i, j+1, k+1) or dfs(i, j-1, k+1))13        board[i][j] = tmp                # 回溯还原14        return found15 16    for i in range(m):17        for j in range(n):18            if dfs(i, j, 0):19                return True20    return False

board[i][j] != word[k] 时立即 return False 是什么思想？

 1def exist(board: list[list[str]], word: str) -> bool: 2    m, n = len(board), len(board[0]) 3  4    def dfs(i: int, j: int, k: int) -> bool: 5        if k == len(word): 6            return True 7        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: 8            return False 9        tmp = board[i][j]10        board[i][j] = '#'                # 占位，防止本路径再次走回来11        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1)12                 or dfs(i, j+1, k+1) or dfs(i, j-1, k+1))13        board[i][j] = tmp                # 回溯还原14        return found15 16    for i in range(m):17        for j in range(n):18            if dfs(i, j, 0):19                return True20    return False

四方向扩展 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 也常被写成什么 Pythonic 形式？

出 dfs 时的 board[i][j] = tmp 若被忘记，会发生什么？

 1def exist(board: list[list[str]], word: str) -> bool: 2    m, n = len(board), len(board[0]) 3  4    def dfs(i: int, j: int, k: int) -> bool: 5        if k == len(word): 6            return True 7        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]: 8            return False 9        tmp = board[i][j]10        board[i][j] = '#'                # 占位，防止本路径再次走回来11        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1)12                 or dfs(i, j+1, k+1) or dfs(i, j-1, k+1))13        board[i][j] = tmp                # 回溯还原14        return found15 16    for i in range(m):17        for j in range(n):18            if dfs(i, j, 0):19                return True20    return False

word="SEE" 在示例 board 中能命中——大致路径是？

本题最坏时间复杂度?

空间复杂度是？

若同时要搜大量 word 列表（→ LC212），怎么改进效率？

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
78	子集	中等	每个元素「选 / 不选」两枝；或固定 start 累加 path（叶子无终止条件）
17	电话号码的字母组合	中等	每层选项是「当前数字对应的若干字母」，而非数组下标
22	括号生成	中等	用「left 还能放几个、right 还能放几个」剪枝，无需事后校验
131	分割回文串	中等	每层枚举切割点；递归 (s[i:]) 处理剩余串

面试常踩

path[:] 拷贝：忘记拷贝就把同一引用塞进 res，最终 res 里全是空 list。等价写法 list(path)。
排列用 used、组合用 start：搞错了不是写不出来——是会少解或多解（[1,2] 与 [2,1] 算一个还是两个）。
进 dfs 改、出 dfs 还原——网格回溯（79、212）的占位法必须配对，少一边就污染棋盘。
N 皇后的对角线身份证：主对角线 row-col 相等，副对角线 row+col 相等——背下来。

回溯 · Backtracking ​

通用模板 ​

关卡 1 · 全排列 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 2 · 组合总和 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 3 · N 皇后 ​

📝 题目

✅ 完整解法

🧠 理解检验

关卡 4 · 单词搜索 ​

📝 题目

✅ 完整解法

🧠 理解检验

同 pattern 索引（hot100 同类题） ​

面试常踩 ​

回溯 · Backtracking

通用模板

关卡 1 · 全排列

关卡 2 · 组合总和

关卡 3 · N 皇后

关卡 4 · 单词搜索

同 pattern 索引（hot100 同类题）

面试常踩