牛客网 面试笔试TOP101 | LeetCode 47. 全排列 II
1. 题目
描述
给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
数据范围： 0 <n≤8 ，数组中的值满足 -1 ≤val≤5
要求：空间复杂度 O(n!)，时间复杂度 O(n!)
示例1
输入：
[1,1,2]
返回值：
[[1,1,2],[1,2,1],[2,1,1]]
示例2
输入：
[0,1]
返回值：
[[0,1],[1,0]]
2. 解题思路
通过回溯法实现数字项的全排列，要特别留意重复数字的处理。具体思路如下：
参考回溯算法模板，进行以下操作：
遍历每一个元素，以该元素作为开头的数字数列。首先选取该数字，并标记该数字已经使用过；再递归选择其他数字；撤销该数字，让其他数字作为开头。缩小数字区间：该元素已经使用过；当前元素与前一个元素一样，且前一个已经使用过。
递归终止条件：选择的数字已经达到n个（数列的长度），则保存选择数字组成的序列，并返回。
如果文字描述的不太清楚，你可以参考视频的详细讲解。
3. 编码实现
核心代码如下：
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @return int整型二维数组
*/
func permuteUnique(num []int) [][]int {
// write code here
result = make([][]int, 0)
path = make([]int, 0)
mark = make([]bool, len(num))
sort.Ints(num)
backtracking(num)
return result
}
func backtracking(num []int) {
// 2.递归终止条件：已经找到一条路径（路径数组满了）,则加入到输出列表
if len(path) == len(num) {
//2.1 存放结果
tmp := append([]int{}, path...) //新建一个切片，如果是引用原来切片，是地址引用，path内容改变时，result数据也会发生改变
result = append(result, tmp)
//2.2 返回
return
}
//1.选择：在本层集合中遍历元素
for i := 0; i < len(num); i++ {
//1.4 剪枝
//1.4.1 元素已经使用过则不需要再加入了
if mark[i] {
continue
}
//1.4.2 当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过
if (i >= 1) && (num[i-1] == num[i]) && mark[i-1] {
continue
}
//1.1 处理节点 （选取数字）
path = append(path, num[i])
mark[i] = true
// 1.2 递归（选择其他数字）
backtracking(num)
//1.3 回溯，撤销选择
path = path[:len(path)-1]
mark[i] = false
}
}
var (
result [][]int //结果集
path []int //路径
mark []bool
)具体完整代码你可以参考下面视频的详细讲解。
4.小结
有重复项数字的全排列可以通过回溯法完成，要特别留意对重复数字的处理。遍历每一个元素，以该元素作为开头的数字数列。首先选取该数字，并标记该数字已经使用过；再递归选择其他数字；撤销该数字，让其他数字作为开头。
《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：
✅ 链表
✅ 二叉树
✅ 二分查找、排序
✅ 堆、栈、队列
✅ 回溯算法
✅ 哈希算法
✅ 动态规划
无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！
Python编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss897667807Golang编码实现：哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss63997
对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
今日佳句：老吾老，以及人之老；幼吾幼，以及人之幼。