数字全排列
题目描述
输入一组数字（可能包含重复数字），输出其所有的排列方式。
数据范围：
- 输入数组长度 [0,6]
- 数组元素取值范围 [1,10]
示例
输入：[1,2,3]
输出：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
输入：[1,1,2]
输出：
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解题思路
方法一：回溯算法（推荐）
核心思想： 使用深度优先搜索（DFS）和回溯的思想，逐个位置选择数字，当选择完所有位置时得到一个排列。
处理重复数字的关键：
- 首先对数组进行排序，让相同数字相邻
- 在同一层递归中，跳过重复的数字（即
nums[i] == nums[i-1] && !used[i-1]） - 使用
used数组标记已使用的数字
算法步骤：
- 对输入数组进行排序
- 使用递归函数
backtrack(path, used) - 如果当前路径长度等于数组长度，将路径加入结果
- 否则遍历数组，选择未使用且不重复的数字加入路径
- 递 归调用，然后回溯（撤销选择）
时间复杂度： O(n! × n)
空间复杂度： O(n)
func permute(nums []int) [][]int {
result := [][]int{}
if len(nums) == 0 {
return result
}
// 排序以便处理重复数字
sort.Ints(nums)
used := make([]bool, len(nums))
path := []int{}
var backtrack func()
backtrack = func() {
// 递归终止条件
if len(path) == len(nums) {
// 重要：需要复制path，否则后续修改会影响结果
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
return
}
for i := 0; i < len(nums); i++ {
// 跳过已使用的数字
if used[i] {
continue
}
// 跳过重复数字（关键去重逻辑）
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue
}
// 做选择
path = append(path, nums[i])
used[i] = true
// 递归
backtrack()
// 撤销选择（回溯）
path = path[:len(path)-1]
used[i] = false
}
}
backtrack()
return result
}
我来详细解释这个题解，帮你理解回溯算法是如何解决数字全排列问题的。
核心概念解释
1. 什么是回溯算法？
回溯算法就像 走迷宫，当走到死路时会回到上一个岔路口，尝试其他路径。在这个问题中：
- 前进：选择一个数字放入当前位置
- 回退：撤销刚才的选择，尝试其他数字
2. 为什么要排序？
原数组：[1,1,2]
排序后：[1,1,2] （相同数字相邻）
排序让相同的数字挨在一起，这样我们就能轻松识别和跳过重复的情况。
详细执行过程
让我用 [1,1,2] 这个例子来演示：
初始状态
nums = [1,1,2] // 已排序
used = [false, false, false] // 标记哪些位置的数字已被使用
path = [] // 当前正在构建的排列
result = [] // 存储所有有效的排列
递归树展示
开始 path=[]
/ | \
选nums[0]=1 选nums[1]=1 选nums[2]=2
path=[1] (跳过重复) path=[2]
| |
选剩余数字 选剩余数字
/ \ / \
选nums[1]=1 选nums[2]=2 选nums[0]=1 选nums[1]=1
path=[1,1] path=[1,2] path=[2,1] path=[2,1]
| | | (跳过重复)
选nums[2]=2 选nums[0]=1 选nums[1]=1
path=[1,1,2] path=[1,2,1] path=[2,1,1]
得到结果： 得到结果： 得到结果：
[1,1,2] [1,2,1] [2,1,1]
关键去重逻辑解释
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue
}
这行代码的意思是：
i > 0：不是第一个元素nums[i] == nums[i-1]：当前数字和前一个数字相同!used[i-1]：前一个相同的数字还没被使用
为什么 要这样判断？
假设我们有两个相同的数字 1₁ 和 1₂（下标分别表示它们在数组中的位置）：
❌ 错误情况：如果我们允许先选 1₂ 再选 1₁，那么：
- 路径1：
1₁ → 1₂ → 2得到[1,1,2] - 路径2：
1₂ → 1₁ → 2得到[1,1,2]（重复！）
✅ 正确做法：强制按顺序使用相同数字，即必须先用 1₁ 才能用 1₂。
!used[i-1] 的含义
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue // 跳过这个选择
}
这个条件的逻辑是：
nums[i] == nums[i-1]：当前数字与前一个数字相同!used[i-1]：前一个相同的数字没有被使用
关键理解：如果前一个相同的数字都没用，那当前这个数字就不应该用！
图解说明
以 [1,1,2] 为例：
[]
/ | \
nums[0] nums[1] nums[2]
1₁ 1₂ 2
/ | \
[1₁] [1₂] [2]
↑
跳过这个分支！
为什么跳过 [1₂]？
- 当我们在第一层选择时，遇到第二个1（
nums[1]） - 发现
nums[1] == nums[0]（都是1） - 且
!used[0]为 true（第一个1没有被使用） - 所以跳过，避免重复
详细执行过程
// 数组: [1,1,2]，索引: [0,1,2]
// used: [false, false, false]
// 第一层递归
i=0: nums[0]=1, 选择 ✓
i=1: nums[1]=1, nums[1]==nums[0] && !used[0], 跳过 ✗
i=2: nums[2]=2, 选择 ✓
// 这样确保在同一层级，相同数字只选择第一个出现的
具体执行步骤
第1步：选择 nums[0]=1
path = [1]
used = [true, false, false]
第2步：在剩余数字中选择
- 跳过
nums[0]（已使用） - 选择
nums[1]=1
path = [1, 1]
used = [true, true, false]
第3步：选择最后一个数字 nums[2]=2
path = [1, 1, 2] // 长度等于nums长度，找到一个完整排列！
result = [[1,1,2]]
第4步：回溯，撤销第3步的选择
path = [1, 1]
used = [true, true, false]
没有其他数字可选，继续回溯...
代码中的关键点
1. 深拷贝的重要性
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
如果直接用 result = append(result, path)，后续对 path 的修改会影响已保存的结果。
2. 回溯操作
// 做选择
path = append(path, nums[i])
used[i] = true
// 递归探索
backtrack()
// 撤销选择（回溯）
path = path[:len(path)-1]
used[i] = false
时间和空间复杂度
-
时间复杂度 O(n! × n)：
- 总共有 n! 个排列
- 每个排列需要 O(n) 时间复制到结果中
-
空间复杂度 O(n)：
used数组：O(n)path数组：O(n)- 递归栈深度：O(n)
希望这个解释能帮你理解回溯算法的思路！关键是要理解"选择-递归-撤销"这个三步循环，以及如何通过排序和条件判断来避免重复。
方法二：字典序生成法
思想： 基于字典序生成下一个排列的算法，从最小排列开始，依次生成所有排列。
步骤：
- 对数组排序得到最小排列
- 重复使用"下一个排列"算法直到没有下一个排列
时间复杂度： O(n! × n)
空间复杂度： O(1)
关键点总结
- 去重机制： 排序后，在同一层递归中跳过相同数字
- 回溯思想： 选择→递归→撤销选择
- 深拷贝： 将路径加入结果时需要复制，避免引用问题
- 剪枝优化： 及时跳过不符合条件的分支
复杂度分析
- 时间复杂度： O(n! × n)，其中 n! 是全排列的数量，n 是复制每个排列所需的时间
- 空间复杂度： O(n)，递归调用栈的深度和临时数组的空间