一、题目描述
给定一个可包含重复数字的序列 nums
,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
二、思路分析
这道题并不难,是在全排列的基础上进行了小小的加强操作,假设我们把元素放在树的节点上,那么全排列就是对一棵树进行深度优先遍历,记录根节点到每个叶子节点上的路径。
但是题目信息中重点描述了一个信息,数组包含重复元素。那么就意味着元素重复的时候,肯定会出现重复的排列,这时候就需要考虑去重。
假设我们现在使用元素[1, 1, 2]
进行全排列,这时候我们使用一棵树表示全排列可能出现的全部情况,这里不使用数组中的元素放在节点位置,使用的是数组下标。
通过这棵树我们会发现,因为第一个元素和第二个元素相同,所以下标排列1->2->3
和2->1->3
得到排列相同,都是112
,这时候就要考虑去重的。
那该如何去重呢?
首先考虑一个保存和查询方法:那就是对遍历过的路径做个记录,我们可以把记录的排列转化成字符串,添加到一个集合中,每次添加新字符串之前,先查询集合是否存在相同的集合,如何存在则不添加。
此法可行,就是有些繁琐和增加空间复杂度,那么是不是还有更加优雅的解法呢?
我们换一种思路,我们先来思考一下什么情况下会出现重复的排列,那就是在同一个位置上遍历相同的元素,还用上面数组举例,就是在第一个位置上遍历两个1
,那么就多了一种去重的选择:同一个循环里面不要出现同样的元素。
假设我们给相同的元素定个顺序,每次遇到重复元素的时候,只使用第一次出现的那个元素。这样就把这个题转化成了:如何在回溯的过程中,保证如何使用第一次出现的那个元素?
一般在全排列的过程中,我们需要记录已经使用过的元素,那么在同一个循环中就会出现这么一个有趣的场景,每次选择一定是在为当前未使用的元素中选择一个元素填补当前节点位置。
也就是说这次循环遍历到一个元素时,除了这个元素之外的其他的元素的标记在本次循环中的标记是未使用(如果标记为已使用,一定是上一层使用到的)。
如果第二次遇到一个相同的元素,并且与它相同的另一个元素是未使用的标记,那个这个位置上已经选过这个值的元素了,可以直接跳过去了
实现代码前还有一点要注意,题目没有说明给的数组元素是有序的,所以在操作之前,我们需要进行一次排序操作。
示例代码
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private LinkedList<Integer> list = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
backTrack(nums, new boolean[nums.length]);
return ans;
}
public void backTrack(int[] nums, boolean[] status) {
// 全排列结束
if (list.size() == nums.length) {
ans.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
// 如果已经使用过的元素,直接跳过
if (status[i]) {
continue;
}
// 如果不是第一次遇到这个元素,并且上一次遇到的元素未使用,直接跳过
// 上次的元素标记为未使用时,按照顺序实际为使用后释放出来的
if (i > 0 && nums[i] == nums[i - 1] && !status[i - 1]) {
continue;
}
status[i] = true;
list.addLast(nums[i]);
backTrack(nums, status);
list.removeLast();
status[i] = false;
}
}
}
总结
全排列的问题,主要的思想还是回溯算法,这里的重点是注意一下去重,也可以说是树的剪枝。可以试着把问题转化一下,转化成元素身上做一些考虑,或许能看到不一样的解法。