全排列（Permutations）
全排列题的本质不是“生成所有顺序”，而是维护一个路径，再保证每个元素在当前路径里只出现一次。
题目定义
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
示例:
输入: nums = [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
输入: nums = [0,1]
输出: [[0,1],[1,0]]
输入: nums = [1]
输出: [[1]]
核心思路
使用回溯算法穷举所有排列：
- 选择：从剩余元素中选择一个
- 探索：递归生成剩余元素的排列
- 撤销：回溯，尝试其他选择
决策树示例 [1,2,3]:
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2][1,3] [2,1][2,3] [3,1][3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 回溯法 | O(n × n!) | O(n) | n!个排列，每个O(n)复制 |
| 迭代法 | O(n × n!) | O(n × n!) | 需要存储所有中间结果 |
| 交换法回溯 | O(n × n!) | O(n) | 原地交换生成排列 |
Go 代码
used 数组写法
package main
import "fmt"
func permute(nums []int) [][]int {
result := [][]int{}
visited := make([]bool, len(nums))
path := []int{}
var backtrack func()
backtrack = func() {
// 终止条件
if len(path) == len(nums) {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
return
}
// 遍历所有元素
for i := 0; i < len(nums); i++ {
if visited[i] {
continue
}
// 做选择
path = append(path, nums[i])
visited[i] = true
// 递归
backtrack()
// 回溯
path = path[:len(path)-1]
visited[i] = false
}
}
backtrack()
return result
}
// 方法2: 交换元素
func permuteSwap(nums []int) [][]int {
result := [][]int{}
var backtrack func(start int)
backtrack = func(start int) {
// 终止条件
if start == len(nums) {
temp := make([]int, len(nums))
copy(temp, nums)
result = append(result, temp)
return
}
// 遍历从start开始的所有位置
for i := start; i < len(nums); i++ {
// 交换
nums[start], nums[i] = nums[i], nums[start]
// 递归
backtrack(start + 1)
// 回溯
nums[start], nums[i] = nums[i], nums[start]
}
}
backtrack(0)
return result
}
func main() {
nums := []int{1, 2, 3}
result := permute(nums)
fmt.Println("所有全排列:")
for _, perm := range result {
fmt.Println(perm)
}
}这里最关键的不变量是：
path里存的是当前已经选过的数字。visited[i] == true表示nums[i]已经在当前路径里。- 当
len(path) == len(nums)时，说明一条完整排列已经构造完成。
思路展开
回溯过程详解
nums = [1, 2, 3]
=== 第1层：选择第1个元素 ===
选择1: path=[1], choices=[2,3]
选择2: path=[2], choices=[1,3]
选择3: path=[3], choices=[1,2]
=== 第2层：选择第2个元素（以path=[1]为例）===
path=[1], 可选[2,3]
选择2: path=[1,2], choices=[3]
选择3: path=[1,3], choices=[2]
=== 第3层：选择第3个元素 ===
path=[1,2], 可选[3]
选择3: path=[1,2,3], choices=[] ✓ 收集结果
path=[1,3], 可选[2]
选择2: path=[1,3,2], choices=[] ✓ 收集结果
回溯到第1层，尝试选择2...
去重策略详解
有重复元素: [1, 1, 2]
排序后: [1, 1, 2]
树形结构:
[]
/ | \
[1] [1]× [2]
/ \ / \ / \
[1,2][1,1] [1,2]×[1,1]×[2,1][2,1]×
| | | | | |
[1,2,1][1,1,2] ... ... [2,1,1] ...
× 标记的是被剪枝的分支
去重条件:
if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:
continue
解释:
- i > 0: 不是第一个元素
- nums[i] == nums[i-1]: 当前元素与前一个相同
- not visited[i-1]: 前一个未被使用
→ 说明在同一层（树的横向）重复了，需要剪枝
两种常见写法对比
方法1: visited数组
优点: 清晰易懂，容易处理重复元素
缺点: 需要O(n)额外空间
方法2: 交换元素
优点: 原地操作，空间O(1)
缺点: 不易理解，处理重复元素复杂
经典题目
LeetCode 问题
扩展问题
- 字符串的排列
- 字典序的第k个排列
易错点
全排列的 bug 基本都出在“状态没有完全恢复”。
- 收集答案时一定要拷贝
path。 visited[i] = true之后，递归回来必须改回false。- 有重复元素时要先排序，再做树层去重。
- 交换法写起来更短，但更容易把交换还原漏掉。
优缺点
优点
- ✅ 保证完整：生成所有排列
- ✅ 易于理解：递归思路清晰
- ✅ 可扩展：容易处理各种约束
缺点
- ❌ 时间复杂度高：O(n × n!)
- ❌ 空间消耗：递归栈深度O(n)
- ❌ 大规模问题：n > 10时性能差