第7章｜回溯与搜索
Unit 03 · LeetCode #46 · 重构版
← Unit 02
46
Permutationsused · Position · Restore
每一层填写一个位置，
每次返回同时恢复两份状态。
组合只关心选择了哪些元素；排列还关心它们被放入哪个槽位。递归深度表示当前待填位置，每层扫描全部索引，并用 used[index] 排除当前路径已经占用的元素。
LeetCode #46 题目模型不同整数的全部位置顺序
题目要求
给定一个不含重复数字的整数数组 nums，返回所有可能的全排列，顺序任意。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
pass
- 每个输入索引在一个排列中恰好使用一次；
- 不同位置顺序属于不同答案；
- 长度为 n 的输入共有 n! 个排列。
示例与核心契约
nums = [1,2,3]
输出：123、132、213、231、312、321
输出：123、132、213、231、312、321
进入 backtrack() 时，path 已填满前 len(path) 个槽位；used[i] 与索引 i 是否出现在 path 中严格一致。
Position-driven
递归深度表示当前待填槽位，不是候选窗口起点。
used Array
记录当前路径占用的索引，使每层仍可扫描全部元素。
Double Restore
返回时既要 pop path，也要把 used[index] 恢复为 False。
Factorial Output
共有 n! 个叶节点，复制答案的输出成本为 O(n·n!)。
1. 顺序改变答案
2. used 槽位契约
3. Lock—Unlock
4. 错误恢复实验
5. 槽位＋真实轨迹
6. 迁移 #47
环节 1/6
nums=[1,2,3]｜排列状态空间每层填写一个槽位
状态空间树
当前排列状态
候选元素池
used 索引状态
已确认的完整排列
当前状态解释
排列搜索契约
组合与排列的状态差异
搜索事件记录
当前 path[]
当前 depth0
可用索引0,1,2
答案条件len(path)==len(nums)
选择动作lock + append
恢复动作pop + unlock
占用不变量
位置不变量
已确认排列0 / 6
当前深度0
可用元素数3
锁定索引数0
状态是否一致是
先切换三个实验，再根据当前显示的错误状态完成判断。
关键槽位补全先选槽位 → 再选代码
槽位只说明“这一行负责什么”；右侧标签只显示代码。每次填充后必须重新选择下一个槽位。
实时拼接后的代码骨架0 / 6
当前认知焦点
此刻应该理解什么
current
visited（可视化）
queue不适用：本题使用 DFS 递归栈
递归栈
代码 × 状态逐行联动高亮后状态
状态依赖问题
这是理解检查，不是动画门禁；即使不回答，也可以继续下一步或自动播放。
独立完成｜关闭槽位提示后，从空白结构自己写
返回前一步不会降低最大已解锁步骤
第7章 Unit 03 Skill 卡
全排列将回溯从“单向候选窗口”切换为“槽位驱动的占用搜索”。每个子调用都必须看到 path 与 used 完全一致；重复值场景再增加排序与同层去重。
主状态path + used 索引数组
层的含义当前待填排列位置
候选规则每层扫描所有 used=False 索引
答案条件len(path)==len(nums)
双重恢复path.pop() + used[index]=False
#47 增量排序 + 同层跳过等价副本
复杂度输出成本 O(n·n!)
常见错误误用 start、漏解锁、记录前缀
下一题#90 子集 II
环节完成当前状态会保留；你可以继续观察，也可以随时切换到任意环节。