全排列

怎样从“nums=[1,2,3] 是三张号码牌，要排进 slot 0、slot 1、slot 2 三个座位。只要顺序不同，就算不同答案。”推导出 回溯 · 全排列，并证明每次状态变化都不会漏掉答案？

中心结论：每一层递归负责填一个座位；path 表示当前已经坐好的座位顺序，used 表示哪些号码牌已经被拿走，depth=len(path)，i 是当前层 for 循环正在检查的号码牌下标；坐满后复制 path 放入 res，再撤销 path 和 used，恢复现场后换下一张牌。

给定一个没有重复数字的序列，返回其所有可能的全排列。

在本站主例中，nums=[1,2,3] 是三张号码牌，要排进 slot 0、slot 1、slot 2 三个座位。只要顺序不同，就算不同答案。

算法最终需要得到或观察：依次得到 [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。

先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“选择树与撤销绳”，明确答案需要观察什么。
2. 2状态只维护 depth、i、path、used、res.length、当前分支。
3. 3转移每一步按照 每一层递归负责填一个座位；path 表示当前已经坐好的座位顺序，used 表示哪些号码牌已经被拿走，depth=len(path)，i 是当前层 for 循环正在检查的号码牌下标；坐满后复制 path 放入 res，再撤销 path 和 used，恢复现场后换下一张牌。
4. 4收尾读取 依次得到 [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。，并复核边界与复杂度。

路径记录已做选择，候选集合决定下一步，撤销保证兄弟分支互不污染。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：depth、i、path、used、res.length、当前分支。

求出一个数组的排列组合中的所有排列，用 DFS 深搜即可。

每一层递归负责填一个座位；path 表示当前已经坐好的座位顺序，used 表示哪些号码牌已经被拿走，depth=len(path)，i 是当前层 for 循环正在检查的号码牌下标；坐满后复制 path 放入 res，再撤销 path 和 used，恢复现场后换下一张牌。

执行过程中持续维护：depth、i、path、used、res.length、当前分支。

正确性依赖以下不变量：path 长度 d 时恰好填好了前 d 个座位，并且 used=true 的号码牌正好就是 path 里的数字。；同一条路径中每个数字最多出现一次，所以不会重复。；每一层 for 循环都会尝试所有未使用数字，所以不会漏。

面试时可以压缩为：标准排列回溯：一层填一个位置；for 循环枚举所有未 used 的数字；选择后递归，回来后 path = path[:len(path)-1] 与 used[i]=false 恢复现场；path 长度等于 n 时 tmp := append([]int{}, path...) 复制答案。时间 O(n × n!)，辅助空间 O(n)。

落到当前题，执行机制可以压缩为：每一层递归负责填一个座位；path 表示当前已经坐好的座位顺序，used 表示哪些号码牌已经被拿走，depth=len(path)，i 是当前层 for 循环正在检查的号码牌下标；坐满后复制 path 放入 res，再撤销 path 和 used，恢复现场后换下一张牌。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums=[1,2,3] 是三张号码牌，要排进 slot 0、slot 1、slot 2 三个座位。只要顺序不同，就算不同答案。 因为：每一层递归负责填一个座位；path 表示当前已经坐好的座位顺序，used 表示哪些号码牌已经被拿走，depth=len(path)，i 是当前层 for 循环正在检查的号码牌下标；坐满后复制 path 放入 res，再撤销 path 和 used，恢复现场后换下一张牌。
2. 2depth=1：扫描 nums[1]=2扫描光标移动到 2。used[1]=false，说明这张号码牌还可以放进 slot 1。 因为：每一层递归只负责填一个座位，for 循环会扫描所有还没用过的号码牌。
3. 3depth=2：扫描 nums[2]=3扫描到 3，used[2]=false。最后一个座位可以放 3。 因为：每一层递归只负责填一个座位，for 循环会扫描所有还没用过的号码牌。
4. 4depth=2 没有更多选择第 3 个座位这一层没有更多可选数字了，返回上一层。 因为：每一层递归只负责填一个座位，for 循环会扫描所有还没用过的号码牌。
5. 5进入 depth=3：再次坐满path 长度再次等于 nums 长度，当前叶子是一张完整排列。 因为：每一层递归只负责填一个座位，for 循环会扫描所有还没用过的号码牌。
6. 6root：扫描 nums[1]=2第一层 for 循环继续。现在检查 2 能不能作为第一个座位。 因为：每一层递归只负责填一个座位，for 循环会扫描所有还没用过的号码牌。
7. 7选择 3：形成前缀 [2,3]同一层换下一个可选号码牌，slot 1 改放 3。 因为：每一层递归只负责填一个座位，for 循环会扫描所有还没用过的号码牌。
8. 8收尾与复杂度依次得到 [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。 因为：时间 O(n × n!) · 空间 O(n) 辅助；含输出 O(n × n!)。每一层递归负责填一个座位；path 表示当前已经坐好的座位顺序，used 表示哪些号码牌已经被拿走，depth=len(path)，i 是当前层 for 循环正在检查的号码牌下标；坐满后复制 path 放入 res，再撤销 path 和 used，恢复现场后换下一张牌。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return [][]int{}
	}
	used, p, res := make([]bool, len(nums)), []int{}, [][]int{}
	generatePermutation(nums, 0, p, &res, &used)
	return res
}

func generatePermutation(nums []int, index int, p []int, res *[][]int, used *[]bool) {
	if index == len(nums) {
		temp := make([]int, len(p))
		copy(temp, p)
		*res = append(*res, temp)
		return
	}
	for i := 0; i < len(nums); i++ {
		if !(*used)[i] {
			(*used)[i] = true
			p = append(p, nums[i])
			generatePermutation(nums, index+1, p, res, used)
			p = p[:len(p)-1]
			(*used)[i] = false
		}
	}
	return
}

func main() {
    // 1. 主例
    //    输入：mode="permutations", nums=[1,2,3]
    //    期望：依次得到 [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。
    //
    // 2. 失败 / 未命中
    //    检查：忘记 used[i] = false：后续分支会漏答案。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC77 组合；LC78 子集；LC47 全排列 II
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[1,2,3] 是三张号码牌，要排进 slot 0、slot 1、slot 2 三个座位。只要顺序不同，就算不同答案。
2. 2重复先生成全部结果再过滤会探索大量无效分支；回溯在选择阶段剪枝，并在返回时恢复现场。
3. 3优化每一层递归负责填一个座位；path 表示当前已经坐好的座位顺序，used 表示哪些号码牌已经被拿走，depth=len(path)，i 是当前层 for 循环正在检查的号码牌下标；坐满后复制 path 放入 res，再撤销 path 和 used，恢复现场后换下一张牌。
4. 4证明path 长度 d 时恰好填好了前 d 个座位，并且 used=true 的号码牌正好就是 path 里的数字。；同一条路径中每个数字最多出现一次，所以不会重复。；每一层 for 循环都会尝试所有未使用数字，所以不会漏。
5. 5复杂度时间 O(n × n!)，空间 O(n) 辅助；含输出 O(n × n!)