LeetCode 回溯专题
8 道题，建立系统的搜索思维
从“选什么、何时收集、如何撤销”出发，用 Python 3 把组合、排列、约束构造、字符串切分与棋盘搜索连成一条清晰的学习路线。
回溯的核心：在隐式决策树上进行深度优先搜索。沿一条路径做选择，必要时剪枝，保存合法答案，再恢复状态去尝试下一条路径。
讲解、代码、图示与交互均已内置。原题链接是可选在线入口，不影响离线阅读。学习记录保存在当前浏览器；移动文件、更换浏览器或清理浏览器数据可能使记录无法沿用。
学习路线：先定义状态，再写递归
| 阶段 | 题目顺序 | 本阶段重点 |
|---|---|---|
| 1. 基础知识与核心模板 | 78 子集 → 77 组合 | 从子集到定长组合 |
| 2. 典型应用：排列与多叉选择 | 46 全排列 → 17 电话号码的字母组合 | 区分候选来源与位置状态 |
| 3. 典型应用：约束与剪枝 | 22 括号生成 → 39 组合总和 | 让无效分支尽早停止 |
| 4. 进阶算法：切分与约束搜索 | 131 分割回文串 → 51 N 皇后 | 预处理协作与位运算优化 |
理解回溯：递归、DFS 与恢复状态
递归是函数调用方式；DFS 是优先走深的遍历策略；回溯强调尝试选择并恢复现场。搜索树无需显式建出来：每个节点是一份已作出的决定，每条边是一次新选择，递归参数描述下一步的限制。
纵向看深度：已经决定多少元素、位置、字符段或棋盘行。横向看分支：当前一步可以尝试哪些候选。for 循环枚举同一层，递归进入下一层；不要把循环次数与递归层数混为一谈。
核心模板：用四个问题确定搜索
| 设计问题 | 需要明确的内容 | 本专题例子 |
|---|---|---|
| 状态是什么？ | path + 描述下一步的参数 | start、位置 i、remain、左右计数、row |
| 哪些候选合法？ | 范围、已用状态、约束 | used[i]、value≤remain、right<left、斜线未占用 |
| 何时收集？ | 每个节点还是完成状态 | 子集每节点；排列长度 n；切分 start=n |
| 什么要撤销？ | 共享可变状态 | append/pop，add/remove，交换/交换回来 |
参数与共享变量：整数、字符串参数产生新值时无需改回；外层列表和集合被原地修改时必须恢复。列表答案用 copy，字符串答案用 join。所有解法都使用局部 ans，重复调用同一个 Solution 实例不会残留上次答案。
证明三个落点：合法性：只扩展合法状态；完整性：任一答案对应未被剪掉的路径；唯一性：递增下标、位置选择或唯一切分序列避免重复。
交互推演：观察选择、保存和撤销
用 78 题主解走一遍 nums=[1,2]。“保存”复制当前 path；回到父层不会删除已保存的答案。
第 1 阶段 · 基础知识与核心模板
从子集到定长组合。
01LEETCODE 78子集
题意与边界
给定元素互不相同的整数数组 nums，返回所有子集，包括空集与全集。子集不考虑排列顺序，答案中不能重复。原题 1 ≤ n ≤ 10，元素可为负数；可用性由下标决定，不能用数值大小判断。
解题思路一：枚举下一个元素（主解）
把 dfs(start) 定义为：路径已固定，接下来只能选择下标 ≥ start 的元素。进入函数时，当前路径本身已经是一个合法子集，立即保存快照。再枚举下一个元素，递归传入 i+1。下标严格递增，使同一批元素只按一种顺序生成。
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans, path = [], []
def dfs(start: int) -> None:
ans.append(path.copy())
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return ans
关键代码解释
ans.append(path.copy())在每个节点执行，根节点保存 []；若仅在叶子保存，会漏掉短子集。dfs(i + 1)同时保证一个元素最多使用一次、不会出现 [2,1] 这样的重排重复。path.pop()恢复进入当前选择前的路径，下一分支才能从相同父状态出发。
示例推演
输入：nums = [1,2,3]
输出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]| 事件 | path | 发生了什么 |
|---|---|---|
| 进入 dfs(0) | [] | 保存空集 |
| 选 1 → dfs(1) | [1] | 保存 [1] |
| 选 2 → dfs(2) | [1,2] | 保存 [1,2] |
| 选 3 → dfs(3) | [1,2,3] | 保存全集，循环为空 |
| 弹出 3，再弹出 2 | [1] | 回到 [1] 所在层，继续选 3 |
| 选 3 → dfs(3) | [1,3] | 保存后撤销，再回根节点选 2、3 |
时间复杂度与空间复杂度
共有 2ⁿ 个子集，所有结果的元素总数为 n·2ⁿ⁻¹（n≥1）。时间 Θ(n·2ⁿ)，由复制输出主导；辅助空间 O(n)（路径与递归栈）；输出空间 Θ(n·2ⁿ)。
解题思路二：每个元素选或不选
固定处理下标 i，只有“不选 nums[i]”与“选 nums[i]”两个分支。所有决策结束后才收集答案；这与主解在每个节点收集的方式不同。
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans, path = [], []
def dfs(i: int) -> None:
if i == len(nums):
ans.append(path.copy())
return
dfs(i + 1) # 不选
path.append(nums[i])
dfs(i + 1) # 选
path.pop()
dfs(0)
return ans
关键是 i==len(nums) 才保存；每层都前进到 i+1。对 [1,2]，四片叶子依次为 []、[2]、[1]、[1,2]。时间 Θ(n·2ⁿ)，辅助空间 O(n)，输出 Θ(n·2ⁿ)。
解题思路三：位掩码枚举
用 n 位二进制数表示是否选择每个下标，枚举 0 到 2ⁿ−1。第 i 位为 1 就收录 nums[i]；例如 [1,2,3] 的掩码 101 表示 [1,3]。
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
for mask in range(1 << n):
subset = []
for i in range(n):
if mask & (1 << i):
subset.append(nums[i])
ans.append(subset)
return ans
时间 Θ(n·2ⁿ)，结果之外辅助空间 O(n) 用于当前构造的子集（本题范围内，掩码按固定字长计）；无递归栈。
| 解法 | 优点 | 取舍 |
|---|---|---|
| 枚举下一个 | 直接迁移到组合、组合总和 | 需要理解每个节点都可收集 |
| 选或不选 | 决策树直观 | 固定走到第 n 层才保存 |
| 位掩码 | 无需递归，状态紧凑 | 不便按复杂约束提前剪枝 |
易错点
- 不能直接保存可变路径
ans.append(path)，否则答案共享同一列表。 - 无需排序；原题元素互异，start 控制的是下标顺序。
- 原题不含空数组；若扩展输入 []，三种实现都返回 [[]]，与幂集定义一致。
02LEETCODE 77组合
题意与边界
从整数 1 到 n 中选 k 个不同数字，返回全部组合。原题 1 ≤ k ≤ n ≤ 20，顺序不重要：[1,2] 和 [2,1] 是同一组合。
解题思路一：递增选择 + 上界剪枝（主解）
沿用 dfs(start)，只在路径长度等于 k 时收集。设还缺 need=k−len(path) 个数；本轮选择 x 后，区间 [x+1,n] 必须至少剩 need−1 个数，因此 x≤n−need+1。最后可选值随路径长度变化。
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans, path = [], []
def dfs(start: int) -> None:
if len(path) == k:
ans.append(path.copy())
return
need = k - len(path)
for x in range(start, n - need + 2):
path.append(x)
dfs(x + 1)
path.pop()
dfs(1)
return ans
关键代码解释
- range 不包含右端点，所以写
n - need + 2。 - 传入 x+1，避免重复使用 x，也避免重排组合。
- 达到 k 后必须 return，不再扩展更长路径。
示例推演
输入：n = 4, k = 2
输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]| 当前路径 | 还缺 need | 本层候选 | 效果 |
|---|---|---|---|
| [] | 2 | 1、2、3 | 根节点不选 4：其后已无第二个数 |
| [1] | 1 | 2、3、4 | 保存 [1,2]、[1,3]、[1,4] |
| [2] | 1 | 3、4 | 生成 [2,3]、[2,4] |
| [3] | 1 | 4 | 生成 [3,4] 后结束 |
时间复杂度与空间复杂度
设 B=C(n,k)。剪枝后每个访问到的前缀都能完成为答案，节点数可用 B 条、每条至多 k 的根叶路径上界计数。复制每个答案也需 O(k)，总时间 O(k·B)；辅助空间 O(k)；输出空间 Θ(k·B)。
解题思路二：选或不选 + 剩余数量剪枝
处理整数 x，分别考虑选与不选。展开前检查 n−x+1 是否足够补齐路径；不足就无需访问整棵子树。
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans, path = [], []
def dfs(x: int) -> None:
if len(path) == k:
ans.append(path.copy())
return
if n - x + 1 < k - len(path):
return
path.append(x)
dfs(x + 1)
path.pop()
dfs(x + 1)
dfs(1)
return ans
n=4,k=2，path=[3]、x=4 时选择 4 得到 [3,4]；不选 4 后 x=5，剩余 0 个数，立即停止。先检查完成条件，再判断余量。保守时间上界 O(n·B)，递归深度可到 n，辅助空间 O(n)，输出 Θ(k·B)。循环法把连续“不选”压缩为枚举，通常更简洁，且栈只需 O(k)。
易错点
- 固定枚举到 n 也正确，但会搜索凑不齐 k 个数的分支；剪枝上界别少 1。
- 无需 used；递增 start 已足够，used 不能代替组合的顺序规范。
- k=n 时仅有 [1,…,n]；k=1 应有每个单元素。扩展 k=0，两实现均返回 [[]]。
第 2 阶段 · 典型应用：排列与多叉选择
区分候选来源与位置状态。
03LEETCODE 46全排列
题意与边界
给定 n 个互不相同的整数，返回全部长度为 n 的排列。原题 1 ≤ n ≤ 6。排列区分顺序，[1,2] 与 [2,1] 必须都出现。
解题思路一：used 标记（主解）
每层决定一个位置放谁。候选始终是所有元素，used[i] 标记下标 i 是否已经出现在当前路径中。长度到 n 才收集。这里不能让 start 单调递增，否则后续无法选择更早元素，会退化为组合。
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ans, path = [], []
used = [False] * len(nums)
def dfs() -> None:
if len(path) == len(nums):
ans.append(path.copy())
return
for i, value in enumerate(nums):
if used[i]:
continue
used[i] = True
path.append(value)
dfs()
path.pop()
used[i] = False
dfs()
return ans
关键代码解释
- used[i] 属于当前路径，不是永久访问标记；兄弟分支仍可用相同元素。
- 选择时同时修改 path 与 used，返回后两个状态都要恢复。
- 用下标标记可用性；原题元素互异，无需额外去重。
示例推演
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]| 操作 | path | used（按下标） |
|---|---|---|
| 选 1 | [1] | [True,False,False] |
| 选 2，再选 3 | [1,2,3] | [True,True,True] |
| 保存，撤销 3 和 2 | [1] | [True,False,False] |
| 选 3，再选 2 | [1,3,2] | [True,True,True] |
| 最终回根节点 | [] | [False,False,False]；可开始选 2 |
时间复杂度与空间复杂度
n! 个答案，每份复制 n 个元素。各层扫描候选的总代价也被 O(n·n!) 覆盖，时间 Θ(n·n!)；辅助空间 O(n)（used、path、栈）；输出空间 Θ(n·n!)。
解题思路二：原地交换
把 nums[0:first] 看成已固定前缀。从 first 到 n−1 选择一个元素，与 first 交换，然后固定下一位置。返回后再次交换恢复。
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
def dfs(first: int) -> None:
if first == len(nums):
ans.append(nums.copy())
return
for i in range(first, len(nums)):
nums[first], nums[i] = nums[i], nums[first]
dfs(first + 1)
nums[first], nums[i] = nums[i], nums[first]
dfs(0)
return ans
例如 [1,2,3] 固定首位 1 后，交换后两位得到 [1,3,2]；交换恢复后，再让 2 到首位。first 表示要填的位置，不是禁止使用较早下标的 start。时间 Θ(n·n!)，辅助 O(n) 仅来自栈，输出 Θ(n·n!)。执行中修改 nums，正常返回时完全恢复。used 法更易增加候选约束，交换法省去 used 与 path 数组。
易错点
- 列表
value in path查询是 O(n)，不能替换索引标记后仍声称查询 O(1)。 - 漏恢复 used 或漏交换回来，会污染后续分支。
- 原题不含重复元素；若允许重复，以上实现需另加同层去重。
- 单元素 [0] 返回 [[0]]；扩展空数组返回 [[]]。
04LEETCODE 17电话号码的字母组合
题意与边界
将只包含 2–9 的数字字符串转换为所有可能字母串。每个数字恰好选一个对应字母，字符顺序与数字位置一致。当前原题长度为 1–4；实现额外兼容空串并返回 []。0 和 1 不属于输入范围。
| 数字 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| 字母 | abc | def | ghi | jkl | mno | pqrs | tuv | wxyz |
解题思路一：按数字位置递归（主解）
dfs(i) 表示前 i 个数字已映射，接下来枚举第 i 个数字的字母。每层候选集合不同，同一字母可以出现在不同位置，无需 used 或 start。到 i=m 时 join 路径。
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
mapping = {"2": "abc", "3": "def", "4": "ghi",
"5": "jkl", "6": "mno", "7": "pqrs",
"8": "tuv", "9": "wxyz"}
ans, path = [], []
def dfs(i: int) -> None:
if i == len(digits):
ans.append("".join(path))
return
for ch in mapping[digits[i]]:
path.append(ch)
dfs(i + 1)
path.pop()
dfs(0)
return ans
关键代码解释
- mapping[digits[i]] 决定当前层的全部分支，而非枚举所有字母。
- join 生成独立字符串，代价 O(m)，不能省略在复杂度分析中。
- 空串特判防止根节点直接收集成 [""]。
示例推演
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]| 层 | 路径变化 | 收集或撤销 |
|---|---|---|
| i=0，数字 2 | [] → [a] | 进入下一层 |
| i=1，数字 3 | [a,d] → [a,e] → [a,f] | 每条长度 2 的路径保存后撤销末位 |
| 回到 i=0 | 撤销 a，再选 b | 得到 bd、be、bf |
| 最后选 c | cd、ce、cf | 共 3×3=9 种 |
时间复杂度与空间复杂度
设 m 为数字个数，a 个数字对应 3 个字母，b 个对应 4 个，P=3ᵃ·4ᵇ，m=a+b。时间 Θ(m·P)，最坏 O(m·4ᵐ)；辅助空间 O(m)；输出 Θ(m·P)。
解题思路二：迭代扩展笛卡尔积
从一个空前缀开始，每读入一个数字，将已有前缀与它的字母两两拼接。无需共享可变路径，也无需撤销。
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
mapping = {"2": "abc", "3": "def", "4": "ghi",
"5": "jkl", "6": "mno", "7": "pqrs",
"8": "tuv", "9": "wxyz"}
result = [""]
for digit in digits:
result = [prefix + ch
for prefix in result
for ch in mapping[digit]]
return result
"23" 的扩展为 [""] → ["a","b","c"] → 九个双字符结果。时间 Θ(m·P)，总峰值空间 O(m·P)；若不计最终结果，构造新一层时仍保留旧一层前缀，辅助空间最坏上界也为 O(m·P)，不能宣称是 DFS 的 O(m)。DFS 易加前缀剪枝，迭代法更短并避开递归。
易错点
- 7、9 各对应四个字母，并非每层都只有三分支。
- digits="22" 应有 "aa"；全局 used 会误删答案。
- 不能排序数字；"23" 与 "32" 的输出位置不同。
- "2" 返回 ["a","b","c"]；空串扩展返回 []。
第 3 阶段 · 典型应用：约束与剪枝
让无效分支尽早停止。
05LEETCODE 22括号生成
题意与边界
给定 n 对括号，生成全部有效括号串。原题 1 ≤ n ≤ 8。有效不仅要求总数匹配，还要求任意前缀中右括号数不超过左括号数。
解题思路：只扩展合法前缀
left、right 分别记录已用的左、右括号数量。还剩左括号时可以添加左括号；仅当 right<left 时可以添加右括号。生成时就排除无效前缀，比先生成 2²ⁿ 个括号串再检验更有效。
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans, path = [], []
def dfs(left: int, right: int) -> None:
if left == n and right == n:
ans.append("".join(path))
return
if left < n:
path.append("(")
dfs(left + 1, right)
path.pop()
if right < left:
path.append(")")
dfs(left, right + 1)
path.pop()
dfs(0, 0)
return ans
关键代码解释
- 两个条件必须是独立的 if：一个前缀可能既能加左括号，也能加右括号。
- right<left 表示当前至少有一个未匹配左括号；仅检查 right<n 不够。
- 递归参数是整数，子调用不会修改父层 left/right；共享列表 path 才需 pop。
示例推演
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]| 前缀 | left / right | 下一步 | 原因 |
|---|---|---|---|
| 空串 | 0 / 0 | 只能加 ( | 右括号会使余额为负 |
| ( | 1 / 0 | 可加 ( 或 ) | 两个独立分支 |
| ((( | 3 / 0 | 只能加 ) | 左括号配额用完 |
| (() | 2 / 1 | 可加 ( 或 ) | 分别通向 (()())、(())() |
| () | 1 / 1 | 只能加 ( | 没有未匹配左括号 |
时间复杂度与空间复杂度
答案数为第 n 个卡特兰数 Cₙ=C(2n,n)/(n+1)，渐近 Θ(4ⁿ/n³ᐟ²)。每个答案长度 2n，所有合法前缀都可延伸到答案，节点可用答案路径覆盖。生成与复制总时间 Θ(n·Cₙ)，即 Θ(4ⁿ/√n)；辅助空间 O(n)（路径与栈深度至多 2n）；输出 Θ(n·Cₙ)。
正确性：每个有效串的前缀均满足约束，故其路径不会被剪掉，保证完整；每条选择序列唯一确定一个字符串，保证不重；达到 n,n 时，计数与前缀都合法。
方法比较
暴力生成所有长 2n 的括号串再检验，需要 O(n·4ⁿ) 时间和 O(n) 工作空间。主解把合法性变为两个局部条件，直接生成合法前缀；这正是本题应掌握的优化，不必先写低效暴力。
易错点
- 把两个 if 写成 if/elif 会漏掉同一前缀下的另一合法选择。
- right≤left 会在相等时放入非法右括号，应为严格小于。
- 总数相等并不意味着有效，例如 ")("。
- n=1 返回 ["()"]；扩展 n=0 返回 [""]，表示唯一空构造。
06LEETCODE 39组合总和
题意与边界
给定互不相同的正整数 candidates 和正目标 target，返回全部和为 target 的不同组合。同一数字可无限次使用，组合内部顺序不重要。原题候选数 1–30，数值 2–40，target 为 1–40；正数保证递归终止。
解题思路：递增下标 + 允许复用当前位置
dfs(start,remain) 表示接下来只选 start 及之后的候选，还需凑 remain。先排序，遇到候选大于 remain 时 break，后续更大值同样不可选。选择下标 i 后仍传 i，让它可继续使用；不回到更早下标，消除 [2,2,3] 与 [3,2,2] 的重排重复。
from typing import List
class Solution:
def combinationSum(self, candidates: List[int],
target: int) -> List[List[int]]:
nums = sorted(candidates)
ans, path = [], []
def dfs(start: int, remain: int) -> None:
if remain == 0:
ans.append(path.copy())
return
for i in range(start, len(nums)):
value = nums[i]
if value > remain:
break
path.append(value)
dfs(i, remain - value)
path.pop()
dfs(0, target)
return ans
关键代码解释
- sorted 保留原输入，并让 break 有效；未经排序只能 continue 跳过当前过大值。
dfs(i, remain - value)不能改成 i+1，否则禁止复用，改变题意。- 无需 used；重复使用被允许，重复排列由非递减下标避免。
- remain 是不可变整数，无需手动加回；共享列表 path 仍需恢复。
示例推演
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
边界：candidates = [2], target = 1 → []| 路径 | remain | 下一步与剪枝 |
|---|---|---|
| [] | 7 | 先选 2 |
| [2] | 5 | 仍可从下标 0 选 2 |
| [2,2] | 3 | 尝试 2 后剩 1，无候选可选；退回再选 3 |
| [2,2,3] | 0 | 保存；逐层撤销 |
| [3] | 4 | 再选 3 后剩 1；遇 6>4 时 break |
| [7] | 0 | 保存第二个答案 |
时间复杂度与空间复杂度
设 m 为候选数，D=⌊target/min(candidates)⌋ 为最大路径长度，R 为答案数，S 为所有输出组合长度之和，V 为实际访问节点数。排序 O(m log m)。循环每一次成功尝试生成一条边，每个节点至多另遇一次 break，所以搜索 O(V)，结果复制 O(S)。总时间 O(m log m+V+S)。
只依赖输入参数的安全上界：深度 d 的非递减下标序列至多 C(m+d−1,d) 种；0 到 D 层合计至多 C(m+D,D) 个节点。于是时间上界为 O(m log m+C(m+D,D)+R·D)。这不是精确等式，正数和目标限制会剪掉很多节点；不能统一写 O(2ᵐ)，因为元素允许重复。辅助空间 O(m+D)（排序副本及工作区、路径、栈），输出空间 O(R+S)。
终止与剪枝都依赖正数条件。允许 0 会使重复选择时 remain 不变；允许负数会使 value>remain 的剪枝失效，这些均不属于原题。
易错点
- 不能把 start 重置为 0，否则会按多种顺序生成同一组合。
- 不能为了“去重”而禁止同一个数再次出现。
- [7]、target=7 应返回 [[7]]；无解返回 []，不是 [[]]。
- 本题候选互异，无需邻值去重；不要混用含重复候选题目的规则。
第 4 阶段 · 进阶算法：切分与约束搜索
预处理协作与位运算优化。
07LEETCODE 131分割回文串
题意与边界
把字符串 s 切为若干连续非空子串，要求每一段都是回文，返回全部方案。每个字符按原序恰好覆盖一次。原题 1 ≤ n ≤ 16，只含小写字母；不能跳字符或重新排列字符。
解题思路一：枚举段尾 + 即时回文检查
dfs(start) 表示 s[:start] 已合法切分，接下来选择下一段的右端 end。若 s[start:end+1] 为回文就加入路径，继续从 end+1 切下一段。只有 start==n 才覆盖了完整字符串。
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans, path = [], []
def dfs(start: int) -> None:
if start == len(s):
ans.append(path.copy())
return
for end in range(start, len(s)):
piece = s[start:end + 1]
if piece != piece[::-1]:
continue
path.append(piece)
dfs(end + 1)
path.pop()
dfs(0)
return ans
关键代码解释
- 切片右端不包含，所以写 end+1。
- 长度为 ℓ 时，切片、反转与比较均需 O(ℓ)，并非 O(1)。
- 下一起点必须为 end+1，不能 start+1：每段长度不固定。
- path.copy() 复制字符串引用，字符串不可变，浅拷贝已安全。
示例推演
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
输入：s = "a" → [["a"]]| 起点 | 尝试段 | 结果 |
|---|---|---|
| 0 | a | 回文，从下标 1 继续 |
| 1 | a，再接 b | 到 start=3，保存 [a,a,b] |
| 1 | ab | 非回文，跳过当前段 |
| 0 | aa，再接 b | 保存 [aa,b] |
| 0 | aab | 非回文，结束 |
时间复杂度与空间复杂度
n−1 个缝隙可切可不切，最多 2ⁿ⁻¹ 份答案。直接按“节点×候选段尾×回文长度”放宽可得 O(n²·2ⁿ) 的安全上界；更精细地按 start 分组：到达 start=t 的调用最多 O(2ᵗ)，每次检查所有段的字符工作量 O((n−t)²)，总和 Σ 2ᵗ(n−t)²=O(2ⁿ)。再加保存答案的成本，总时间可收紧为 O(n·2ⁿ)。
辅助空间 O(n)：递归深度 O(n)；活跃路径中的切片覆盖互不重叠的已选前缀，字符总量至多 n；当前回文检查的临时反转串也至多 n。输出空间最坏 O(n·2ⁿ)。共享字符串可减少实际内存，但这里不依赖共享来降低输出上界。
解题思路二：DP 预处理回文表（进阶）
定义 pal[i][j] 表示 s[i:j+1] 是否为回文。两端相等，且内部回文或长度至多 2，就成立。i 从右往左，保证 pal[i+1][j−1] 已算出；回溯时先 O(1) 查表，合法才创建切片。
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
pal[i][j] = (s[i] == s[j] and
(j - i < 2 or pal[i + 1][j - 1]))
ans, path = [], []
def dfs(start: int) -> None:
if start == n:
ans.append(path.copy())
return
for end in range(start, n):
if not pal[start][end]:
continue
path.append(s[start:end + 1])
dfs(end + 1)
path.pop()
dfs(0)
return ans
对 "aab"，单字符表项与 pal[0][1] 为 True；pal[1][2]、pal[0][2] 为 False。搜索分支与直接法一致，合法性改成查表。短路表达式先处理长度 1、2，避免访问不存在的内部区间。
预处理时间、空间 O(n²)；搜索连同切片、输出复制为 O(n·2ⁿ)，总时间 O(n²+n·2ⁿ)；辅助空间 O(n²)，输出 O(n·2ⁿ)。DP 减少重复回文判断，但整体仍受枚举输出限制，不能承诺变为多项式时间。
| 解法 | 优点 | 取舍 |
|---|---|---|
| 直接检查 | 首次学习，代码简洁 | 重复切片与反转 |
| 回文 DP | 合法性 O(1) 查询，适合扩展 | 额外 O(n²) 表，不保证所有输入都更快 |
易错点
- 整串回文时仍需枚举其他分割；"aaa" 有 [a,a,a]、[a,aa]、[aa,a]、[aaa]。
- 不能在中间节点收集，那只是尚未完整覆盖的前缀分割。
- 二维表不能写
[[False] * n] * n，那会让各行共享同一列表。 - 原题字符串非空；扩展空串时两实现返回 [[]]，表示唯一空切分。
08LEETCODE 51N 皇后
题意与边界
在 n×n 棋盘上放 n 个皇后，使任意两者不在同一行、同一列或同一斜线。返回全部棋盘，每行是长度 n 的字符串，Q 为皇后，. 为空格。原题 1 ≤ n ≤ 9；n=2、3 无解。
解题思路一：逐行放置 + 三个集合（主解）
每层固定一行，只放一个皇后，自然排除行冲突。列冲突检查 col；同一条左上到右下斜线的 r−c 相同，同一条右上到左下斜线的 r+c 相同。三个集合只记录已放皇后的占用，放置时加入，退回时删除。
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans, placement = [], []
cols, diag1, diag2 = set(), set(), set()
def dfs(row: int) -> None:
if row == n:
ans.append(["." * c + "Q" + "." * (n - c - 1)
for c in placement])
return
for col in range(n):
if (col in cols or row - col in diag1
or row + col in diag2):
continue
placement.append(col)
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
dfs(row + 1)
diag2.remove(row + col)
diag1.remove(row - col)
cols.remove(col)
placement.pop()
dfs(0)
return ans
关键代码解释
- placement[row]=col 记录每行列号，仅在找到答案后构造 n 行字符串，无需每个节点复制棋盘。
- r−c 可为负，集合可直接保存；改成数组下标时才需偏移 n−1。
- 返回后恢复三类占用和 placement，才能试下一列。
- 每行每列最多一个皇后仍不够，两类斜线也必须检查。
示例推演
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
n = 1 → [["Q"]]；n = 2 或 3 → []| row | col | r−c / r+c | 验证 |
|---|---|---|---|
| 0 | 1 | −1 / 1 | 记录三个集合 |
| 1 | 3 | −2 / 4 | 与上一皇后不同列、不同斜线 |
| 2 | 0 | 2 / 2 | 均未占用 |
| 3 | 2 | 1 / 5 | 得到 [1,3,0,2] |
| 回溯后继续 | [2,0,3,1] | 另一条路径 | 得到第二个棋盘 |
时间复杂度与空间复杂度
令 Q 为答案数。仅考虑列互异，第 r 层至多 P(n,r) 个节点，总计 O(n!)；本实现每个内部节点仍扫描 n 列，安全搜索上界 O(n·n!)。输出每个棋盘还需 n² 个字符，总时间 O(n·n!+Q·n²)，集合查询按平均 O(1) 计。辅助空间 O(n)；输出 Θ(Q·n²)。常见 O(n!) 简写忽略了本实现扫描列与输出构造的成本。
解题思路二：位掩码表示当前行的禁用位置
用 n 位整数表示受攻击列。cols 记录列占用，left、right 表示两种对角线在当前行的攻击位置。可用位置为 full & ~(cols|left|right)。每次取最低有效 1 位放皇后；进入下一行时，两类斜线攻击分别左移、右移一位。
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
full = (1 << n) - 1
ans, placement = [], []
def dfs(cols: int, left: int, right: int) -> None:
if cols == full:
ans.append(["." * c + "Q" + "." * (n - c - 1)
for c in placement])
return
available = full & ~(cols | left | right)
while available:
bit = available & -available
available &= available - 1
placement.append(bit.bit_length() - 1)
dfs(cols | bit, ((left | bit) << 1) & full,
(right | bit) >> 1)
placement.pop()
dfs(0, 0, 0)
return ans
约定第 c 位对应列 c。n=4、首行选 col=1（0010），下一行 cols=0010、left=0100、right=0001，可用位为 1000，只能放 col=3。available & -available 取最低位，available &= available - 1 删除该位。Python 的 ~ 带无限前导 1，必须与 full 做与运算限制范围。
在本题范围的固定字长模型中，按位操作按 O(1) 计；每个状态只枚举合法位置，搜索上界 O(n!)，加输出总时间 O(n!+Q·n²)；辅助 O(n)，输出 Θ(Q·n²)。推广至任意大的 n 时，Python 大整数的按位操作与 bit_length 不能始终视为常数。整数状态传参无需撤销，只有 placement 需 pop。
| 解法 | 优点 | 取舍 |
|---|---|---|
| 三个集合 | 易读，便于现场推导 | 每节点扫描 n 列 |
| 位运算 | 仅枚举可用位置，常数较小 | 需说明范围、位方向、递归状态 |
易错点
- 无需浮点斜率；r−c、r+c 能精确判断斜线。
- 返回棋盘字符串列表，而非列号列表或答案数量。
- 要求全部方案，不能找到第一解就停止，不能擅自去掉镜像答案。
- 位运算对角线掩码表示当前行受攻击位置，集合版存的是固定斜线编号，两种含义不同。
复盘：把八题放在同一张地图上
| 题目 | 状态 / 候选 | 收集条件 | 下一步 / 剪枝 |
|---|---|---|---|
| 78 子集 | start / 后续元素 | 每个节点 | i+1；下标递增 |
| 77 组合 | start / 后续整数 | len(path)=k | x+1；剩余名额上界 |
| 46 全排列 | used / 所有未用元素 | len(path)=n | 标记与恢复下标 |
| 17 电话号码 | 数字位置 i / 对应字母 | i=m | i+1；位置独立 |
| 22 括号生成 | left,right / 两种括号 | left=right=n | left<n，right<left |
| 39 组合总和 | start,remain / 后续候选 | remain=0 | 仍传 i；排序后 break |
| 131 分割回文串 | start / 下一段尾 end | start=n | end+1；只选回文段 |
| 51 N 皇后 | row / 未受攻击列 | row=n | row+1；列与两类斜线 |
start、used 与位置索引，不要混用
无序组合：规范下标顺序消除排列重复；能复用传 i，不能复用传 i+1。排列：每层从全体未用下标中选，需 used 或交换。逐位构造：候选由位置决定，例如电话号码，位置前进即可。连续切分：下一状态为当前段尾之后，不能跳字符。
剪枝必须有理由
| 类型 | 代表 | 不会漏答案的理由 |
|---|---|---|
| 容量不足 | 77 组合 | 剩余元素少于所缺数量，无法完成 |
| 总和超过 | 39 组合总和 | 正数条件下，排序后更大候选同样不能用 |
| 非法前缀 | 22 括号生成 | 负余额前缀不能被后续字符修复 |
| 局部非法 | 131、51 | 非回文段或皇后冲突，后续追加不能改变已有事实 |
复杂度：先计输出，再计搜索
枚举全部答案时，输出规模是时间下界。不能把“每份答案路径深 n”误写成整个算法 O(n)，也不能给所有回溯统一写 O(2ⁿ)。空间要区分辅助状态与最终答案，Python 切片、反转、join 和棋盘构造都要计入。
| 题目主解 | 时间 | 辅助空间 | 输出空间 |
|---|---|---|---|
| 78 子集 | Θ(n·2ⁿ) | O(n) | Θ(n·2ⁿ) |
| 77 组合 | O(k·C(n,k)) | O(k) | Θ(k·C(n,k)) |
| 46 全排列 | Θ(n·n!) | O(n) | Θ(n·n!) |
| 17 电话号码 | Θ(m·P)，P=3ᵃ4ᵇ | O(m) | Θ(m·P) |
| 22 括号生成 | Θ(n·Cₙ) | O(n) | Θ(n·Cₙ) |
| 39 组合总和 | O(m log m+V+S) | O(m+D) | O(R+S) |
| 131 回文 DP | O(n²+n·2ⁿ) | O(n²) | O(n·2ⁿ) |
| 51 集合版 | O(n·n!+Q·n²) | O(n) | Θ(Q·n²) |
m 按具体题目定义为候选或数字个数；D 为 39 题最大深度，V 为搜索节点数，S 为输出元素总数，R 为答案数；P 为 17 题输出串数；Cₙ 为卡特兰数；Q 为 N 皇后解数。表中输出按非空渐近规模描述，空列表本身占常量空间。
掌握程度自测
看懂后再闭卷写一次，并口述不变量。下列勾选独立于题目掌握进度保存。
五天学习计划：练习、复述、隔天再写
| 安排 | 学习内容 | 验收目标 |
|---|---|---|
| Day 1 · 基础 | 核心模板；78 子集、77 组合 | 画搜索树，解释收集位置与剪枝上界 |
| Day 2 · 选择 | 46 全排列、17 电话号码；复写 Day 1 | 不看答案区分 used、start、位置 i |
| Day 3 · 约束 | 22 括号生成、39 组合总和 | 解释两个括号条件与正数剪枝前提 |
| Day 4 · 进阶 | 131 直接法与 DP；51 集合版 | 推导回文转移与对角线编号 |
| Day 5 · 面试 | 51 位运算；闭卷复写 77、39、131、51 | 先状态与不变量，再代码、样例、复杂度 |
| 复习日 | 第 7、14、30 天各抽两题重做 | 无法解释恢复或剪枝就撤销掌握标记，重画树 |
面试表达：先把问题建模清楚
- 识别结果结构。要求所有方案，答案天然对应一棵决策树。
- 定义递归状态。参数表示什么，path 已保证什么？
- 说明候选与剪枝。哪些选择合法，删掉的分支为何无解？
- 写出恢复动作。共享列表、集合如何回到父状态？
- 用小例子验证。包含最小输入、无解与快照独立性。
- 分析复杂度。先答案数量和长度，再搜索与预处理。
最终养成的习惯：用不变量控制正确性，用选择顺序控制重复，用可行性条件控制剪枝，用对称恢复隔离分支。
原题与编写说明
题号、难度、范围与题意对照力扣原题。教学文字、推导、代码与图示为本专题编写；示例按具体代码顺序展示，力扣允许任意答案顺序。全部 Python 代码块均是可独立提交的完整 Solution，不需拼接其他代码块。设计参考本地二叉树学习手册。
原题链接核对日期：2026-10-31。扩展边界已与原题范围区分。浏览器存储受限时，仍可阅读并在当前页面标记。