回溯与约束搜索 · HTML
数学 / 逻辑形态
dfs(start,path) 枚举下一元素 i∈[start,n)。组合递归 dfs(i+1)；允许重复使用时 dfs(i)。在满足目标深度/条件时输出 path 的快照。
识别信号
- 要求列出所有子集、k 组合或满足条件的选取。
- 结果中元素顺序不重要。
- 每个候选可用一次或有限/无限次。
- 需要剪枝但仍必须产生具体解。
- n 较小，输出本身可能指数级。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 只求方案数或可行性 | 若目标维度适中，DP/组合公式避免输出级搜索。 |
| 顺序不同算不同答案 | 那是 permutation/ordered construction，start 会错误消除合法顺序。 |
| 只需遍历全部位集合 | 无复杂约束时 bitmask enumeration 可能更直接。 |
核心不变量
进入 dfs(start) 时，path 中索引严格递增且来自 [0,start) 的既定选择；此调用只生成以该 path 为前缀、下一索引不小于 start 的答案，因此无重复。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 下一可选索引 start、当前 path、剩余名额/目标，以及可增量维护的和或约束。 |
| Transition | 依次选择 i，更新 path/约束，递归到 i+1（或 i），返回后精确撤销。 |
| Frontier / order | 隐式决策树的当前 path；for 循环横向枚举下一选择，递归纵向加深。 |
Python 骨架
def combinations(nums, k):
out, path = [], []
def dfs(start):
if len(path) == k:
out.append(path.copy())
return
need = k - len(path)
last_start = len(nums) - need
for i in range(start, last_start + 1):
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return out
正确性思路
- 任何输出 path 的索引递增，因此每个元素至多使用一次且顺序规范。
- 任意 k 元组合按递增索引有唯一序列；循环会依次选择该序列并到达 base，故不漏。
- 唯一规范序列意味着不会有两条递归路径生成同一索引组合。
复杂度
| Time | Space | Parameters |
|---|
| 输出 k 组合为 Θ(C(n,k)·k)；全子集为 Θ(n·2^n) | O(k) 栈/path，不计输出 | n 为候选数，k 为选择数；输出下界不可消除。 |
边界条件
- k=0
- k>n
- 输入有重复值
- 候选是否可复用
- 输出必须 copy path
- 剪枝使用剩余元素数
错误模式
| Pattern | Why it fails / fix |
|---|
| 递归总从 0 开始 | 同一集合会按多种排列重复生成，并可能重复用元素。 |
| append(path) 不复制 | 所有答案引用同一可变列表，最终一起变空或相同。 |
| 选择后忘记 pop | 兄弟分支继承错误状态；选择与撤销必须镜像。 |
| 值重复时只靠 start | start 防索引排列重复，不防相同值的不同索引生成重复答案；需排序加同层去重。 |
选择与排除规则
- 先判断顺序是否构成不同答案。
- 明确每个候选可用次数，决定 i+1 还是 i。
- 只有需要具体解时接受输出级复杂度。
- 剪枝必须证明被剪分支不可能完成。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 蓝红不会再次出现，因为其索引顺序不规范。 |
| Setup | 从颜色 [红,蓝,绿] 中选 2 种。 |
| Trace | 路径只按索引递增生成 红蓝、红绿、蓝绿。 |
Recall prompts
我的补充