回溯与约束搜索 · HTML
数学 / 逻辑形态
dfs(pos) 为位置 pos 选择任一未使用索引 i，标记 used[i]，递归 pos+1，再撤销。输入排序后，若 nums[i]==nums[i-1] 且前一个相同值尚未在本路径使用，则跳过。
识别信号
- 输出是所有排列或长度固定的有序安排。
- 同一元素不能在一个排列中重复使用。
- 不同选择顺序对应不同答案。
- 需要在每个位置从剩余元素中选一个。
- 输入可能含重复值但答案需唯一。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 顺序不重要的选取 | 应使用 start 组合回溯，排列会产生 k! 重复顺序。 |
| 只求排列数量 | 可用阶乘/多重集合公式或 DP，无需生成。 |
| 位置选择具有局部最优结构 | 若只求最佳排列，可能有贪心、DP 或 assignment 算法，不必列出所有。 |
核心不变量
进入深度 pos 时，path 恰含 pos 个互异索引；used 精确对应 path，且同层相等值只由第一个合法代表扩展。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 当前位置 pos、path、used 布尔数组；或通过交换把 [0,pos) 作为已固定前缀。 |
| Transition | 选择一个未用索引，标记并加入；递归后按相反顺序移除并取消标记。 |
| Frontier / order | 排列树的一层代表一个输出位置；分支数随剩余元素递减。 |
Python 骨架
def unique_permutations(nums):
nums = sorted(nums)
used = [False] * len(nums)
path, out = [], []
def dfs():
if len(path) == len(nums):
out.append(path.copy())
return
for i, value in enumerate(nums):
if used[i]: continue
if i and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True; path.append(value)
dfs()
path.pop(); used[i] = False
dfs()
return out
正确性思路
- used 保证一条根到叶路径每个索引恰用一次，因此叶子是合法排列。
- 对不同值，循环能在每位置选择任一剩余值，故所有排列可达。
- 相等值中只允许当前路径最早未处理代表先被选，消除交换相同值产生的重复而不移除任何值序列。
复杂度
| Time | Space | Parameters |
|---|
| 无重复时 Θ(n·n!)，输出复制占主导 | O(n) 栈/path/used，不计输出 | n 为元素数；重复值将输出数降为 n!/∏c_i!。 |
边界条件
- 空输入是否输出一个空排列
- 重复值
- 对象排序/相等规则
- 只生成前 k 个位置
- 输出复制
- n! 爆炸
错误模式
| Pattern | Why it fails / fix |
|---|
| 用 start 代替 used | start 固定索引递增，只生成组合而非排列。 |
| 重复值去重条件反了 | 应跳过前一个相同值未被使用的情况，保证同层代表顺序。 |
| used 未撤销 | 后续兄弟分支永久丢失候选。 |
| 先生成再用 set 去重 | 浪费指数分支和大量内存；在树上剪掉等价分支。 |
选择与排除规则
- 顺序是否区分答案是第一判断。
- 含重复值时先排序并做同层去重。
- 明确是否真的需要 materialize 全部排列。
- 只求最优排列时寻找更专门模型。
相关模板
| Relation | Template | Boundary |
|---|
| specialization | 约束满足回溯 | 变量是位置、域是尚未使用元素。 |
| contrast | 子集 / 组合回溯 | 顺序不重要，用 start 规范化。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 得到 AAB、ABA、BAA，恰各一次。 |
| Setup | 徽章值 [A,A,B] 的唯一排列。 |
| Trace | 根层若第一个 A 未用，第二个 A 被跳过；在更深层前一 A 已用时，第二 A 可选。 |
Recall prompts
我的补充