全排列：占座、收叶子、把座位还回去
path 是已经坐下的序列，used 是谁被占用。收到 [1,2,3] 后必须弹出 3 并松开标记，[1,3,2] 才能长出来。
回溯：dfs 维护 path 与 used 集合。每层枚举所有下标，跳过 used 的；选入后标记 used 并递归，返回前撤销。path 长度等于 n 时记录。n! 种排列。时间 O(n·n!)，空间 O(n)。
给定一个不含重复数字的数组，返回它所有可能的全排列。每个数字在一个排列里只用一次；答案是全部排列，不是其中一种；中途的前缀还不是答案。
主例 nums = [1, 2, 3]，一共 3!=6 种：[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。组合与子集可以用 start 限制「只能往后选」，排列不行——[1,2] 和 [2,1] 是两个不同答案。
本文要回答的是：每个座位为什么都能选任意还没用过的数，以及收到第一种排列 [1,2,3] 之后，怎样把 path 和 used 一起恢复，现场才干净得能长出 [1,3,2]。
改 path 必改 used，恢复也必须成对
没有回溯时，人会想写三重循环：第一层枚举第一个数，第二层枚举剩下的，第三层枚举最后一个。[1,2,3] 刚好三层，还能写完。数字变成 4 个、8 个，循环层数跟着变，代码写不下去。或者每次「挑一个还没用过的数拼上去」，却忘了退回来——第一种排列做完，path 仍是 [1,2,3]，used 全是真，后面 5 种再也拼不出来。
递归返回后，函数栈退了，你自己改过的切片和布尔数组还在。栈会回去，现场不会自己干净。回溯要你亲手把 path 和 used 恢复到进入这层之前。
把排列想成三个空座位，从左到右填。递归深度是正在填第几个座位。path 是已经坐下去的数字，长度等于深度。used[i] 表示 nums[i] 现在有没有人用。在当前这一层，扫一遍 nums：谁还没被用，谁就可以坐这个座位——推进 path，把对应 used 打真，然后去填下一个座位。从下一层返回之后，立刻做两件镜像的事：path 弹出刚坐的人，used 改回假。
什么时候收集？只有座位坐满，也就是 path 长度等于 3。这时走到叶子，拷贝一份 path 放进答案，然后返回。中途不要收集：[1] 和 [1,2] 还缺座位，不是排列。收集必须拷贝，否则后面的弹出改的是已经放进答案的那一份。
用手走主例到第一片叶子。一开始 path 空，used 全假。深度 0 选 1：path=[1]，used 标记下标 0。深度 1 跳过已用的 1，选 2：path=[1,2]。深度 2 只剩 3：path=[1,2,3]，长度到 3，收集。演示场景前三帧走的就是这一条路。
现场恢复发生在收集之后，这是整篇要看见的一下。深度 2 把 3 弹出：path 从 [1,2,3] 变成 [1,2]，同时松开 3 的 used。深度 2 没有下一个候选了，回到深度 1。深度 1 接着把 2 弹出：path 回到 [1]，2 的 used 松开。深度 1 继续 for，轮到 3：path=[1,3]。下一层只能选 2，走到叶子 [1,3,2]，再收集。没有「弹出 3、松开 3」这一拍，3 会永远占着，[1,3,2] 选不出来。
其余四棵子树同一套节奏。深度 0 选 2，先走 [2,1,3]，pop 回 [2,1]，再走 [2,3,1]；选 3 得到 [3,1,2]、[3,2,1]。每收到一片叶子，都先 pop 回短一截的 path，再试下一个没用过的数。6 种收齐。start 防的是「换序重复」，used 防的是「同一个数用两次」，同时允许任意顺序——这就是排列和组合的分水岭。
used vs startstart 往后走，保持原序，适合组合和子集。[1,2] 和 [2,1] 会被当成同一种。used 允许任意顺序，但每个下标只能用一次。改 path 必改 used，恢复 path 必恢复 used。少一边，树就脏了。
Go：used 回溯
func permute(nums []int) [][]int {res := [][]int{}path := []int{}used := make([]bool, len(nums))var dfs func()dfs = func() {if len(path) == len(nums) {res = append(res, append([]int{}, path...))return}for i, v := range nums {if used[i] { continue }used[i] = truepath = append(path, v)dfs()path = path[:len(path)-1]used[i] = false}}dfs()return res}
1len(path)==n 才收集。主例只有 [1,2,3] 这种满员才进答案，[1,2] 继续往下填。
2for 扫的是「这个座位还能坐谁」。used[i] 为真就跳过，所以 1 不会在同一条路径里坐两次。
3used[i]=true 和 append 是同一拍：占座。dfs 返回后，path 缩回一格、used[i]=false 是同一拍：还座。收到 [1,2,3] 后这两行把现场恢复成 [1,2]。
4append([]int{}, path...) 收下的是拷贝。若不拷贝，后面弹出 3 时，答案里的 [1,2,3] 会变成 [1,2]。
总结
占座改 path 和 used，收到 [1,2,3] 后弹出 3 并松开标记，下一片叶子才是 [1,3,2]。
- 排列关心顺序，不能用 start 只往后选。每个座位枚举所有还没用过的下标。
- 选择和撤销成对：改 path 必改 used，恢复 path 必恢复 used。只改不撤，6 种会收成 1 种。
- 满员才收集，并且必须拷贝 path。中途的 [1]、[1,2] 不是排列。