01先把问题说具体
枚举 [1,2,3] 的所有排列,每个元素恰好使用一次。
02一步步得到方法
把答案想成逐个填好的位置
path 记录已填前缀,used[i] 表示下标 i 的元素是否已使用。到下一位置时尝试每个未使用元素,递归探索以该选择开头的所有可能。长度达到 n 时,一条完整答案产生。
从递归返回后必须撤销本次选择,让同层下一分支面对同样的起始状态。选择、递归、撤销构成一次完整事务;遗漏 pop 或恢复 used 会污染其他分支。
剪枝与去重不是同一件事
used 约束禁止同一位置被选两次,这是合法性检查。若输入值重复,还会生成内容相同的排列,需要排序后在同层跳过等值选择,或按频次枚举;不能简单跳过所有重复值。
本课先限定输入值互异,理解搜索树。以后加约束时,只有能够证明当前前缀不可能扩展成合法答案,才可提前剪掉整个分支。
路径、候选和终止状态要分开
路径记录已经选了什么,候选描述下一步可以选什么,终止条件决定何时收集答案。先画一个两层搜索树,再把进入节点、选择、递归、撤销逐一对应到代码。
剪枝必须证明被删分支不可能产生需要的答案。例如正数和已超过目标时可以剪枝,但若还允许负数,后面的选择可能把和减回来,这条规则就失效。
03把一个小例子完全算清楚
从空前缀枚举 [1,2,3]。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 选 1,再选 2,再选 3 | 记录 [1,2,3] | 叶子达到长度 3 |
| 撤销 3、2,再选 3、2 | 记录 [1,3,2] | 回到前缀 [1] 的另一个分支 |
| 撤销到根,改选 2 | 继续 [2,1,3]、[2,3,1] | 根层状态必须恢复 |
| 根选 3 | 得到另外两种 | 共 3!=6 个答案 |
窄屏可左右滑动表格,阅读完整计算与理由。
回溯是 DFS 的一种状态构造方式;撤销保证不同搜索分支互不干扰。
04为什么这个方法成立
- 每条路径只选未使用下标,因此答案不会重复使用元素。
- 每个位置遍历所有尚未使用的选择,因此每个合法排列都对应一条路径。
- 互异输入下,两个不同选择序列产生不同排列,既完整又无重复。
05把推导翻译成代码
Python · 可独立运行的教学实现
def permutations(a):
result, path = [], []
used = [False] * len(a)
def visit():
if len(path) == len(a):
result.append(path.copy())
return
for i in range(len(a)):
if used[i]:
continue
used[i] = True
path.append(a[i])
visit()
path.pop()
used[i] = False
visit()
return result逐个理解关键决定
path.copy()- 保存当时的快照,不能让所有答案引用同一个稍后会被清空的列表。
used[i] = False- 恢复当前层之前的状态,与 path.pop 成对出现。
06时间、空间与实现范围
输出有 n! 项,每项长度 n,光输出就需要 Θ(n·n!) 时间与空间。
除答案外,path、used 和递归深度均 O(n)。剪枝减少特定输入工作,不自动改变最坏输出下界。
07改变条件,检查哪里会出错
result.append(path)
所有答案会共用一份可变列表;应复制。
认为重复值被 used 自动去重
used 按下标区分,相同值的不同下标仍可产生重复排列。
保存共享路径对象
收集答案时保存 path 本身会让后续撤销影响已收集结果,应保存快照。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
空输入应该有几个排列?
需要一点提示
空选择序列本身是否合法?
查看解析与答案
一个:空排列 [],所以结果为 [[]]。
[1,1,2] 为何得到六条而非三条不同内容?
需要一点提示
两个 1 的下标不同。
查看解析与答案
搜索区分两个 1;要去重需在同层跳过等值选择或按频次构造。
只要第一个满足条件的答案如何提前退出?
需要一点提示
让成功信号沿递归返回。
查看解析与答案
递归返回布尔值,找到后向上传递并停止遍历;若复用状态,仍需确保必要的撤销。