题目来源
题目详情
给定一个可包含重复数字的序列 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</code"><!--=-->-10 <= nums[i] <="10</code"><!--=-->
相似题目
题解详情
本题与[LeetCode-46. 全排列]和[LeetCode-78. 子集]这两道题目都十分相似，主要是递归和回溯算法的考察。
与全排列题目相比，这道题目增加的一个难度就是将无重复元素改成了有重复元素，这就使得我们无法使用全排列这道题目的解题思路来解决问题了。但是，我们需要知道的，我们都需要使用回溯来枚举到所有满足条件的排列，关键是如何筛选掉可能重复的排列。
这里，我们可以首先将数组进行排序，这样就可以使得相同的元素是相邻的，也就减少了我们处理的复杂度。更具体地，我们可以在枚举下标的时候判断前一个元素是否是相同的，如果前一个元素没有遍历过而且是与当前元素相同，那么可以跳过当前元素，因为当前元素一定会被前一个元素枚举在内，这样就达到了去重的目的。
class Solution {
boolean[] vis;// 记录已经遍历过的位置下标
List> result;
public List> permuteUnique(int[] nums) {
vis = new boolean[nums.length];
result = new LinkedList<>();
Arrays.sort(nums);
dfs(nums, 0, new LinkedList());
return result;
}
private void dfs(int[] nums, int num, LinkedList list){
int n = nums.length;
if(num == n){
result.add(new LinkedList(list));
return;
}
for(int i=0; i 0 && !vis[i-1] && nums[i] == nums[i-1])){
continue;
}
vis[i] = true;
list.add(nums[i]);
dfs(nums, num+1, list);
list.removeLast();
vis[i] = false;
}
}
}
Original: https://www.cnblogs.com/GarrettWale/p/16114288.html
Author: Garrett_Wale
Title: LeetCode-47. 全排列 II
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583184/
转载文章受原作者版权保护。转载请注明原作者出处！