原题
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
解法
思想
这道题和leetcode46-全排列的区别在于，数组中会出现相同的数字，对于搜索来说，我们把它想象成树的DFS搜索，就应该避免在同一层搜索到相同值的节点，而不同层之间是允许存在相同值节点的。
我们使用上道题的代码进行改造，如下所示：
代码
class Solution {
List<List<Integer>> ans = new ArrayList<>();
int[] nums;
public List<List<Integer>> permuteUnique(int[] nums) {
int[] used = new int[nums.length];
this.nums = nums;
//要去重，先排序
Arrays.sort(nums);
List<Integer> list = new ArrayList<>();
dfs(list,used,0);
return ans;
}
public void dfs(List<Integer> list,int[] used,int usedCount){
if(usedCount==nums.length){
ans.add(list);
}
for(int i = 0;i<nums.length;i++){
// i == 0，前面没有元素，可以搜索
// used[i-1] == 0，前面的元素在别的层级用过了，可以搜索
// nums[i]!=nums[i-1]，前面的元素和当前元素不相同，可以搜索
if(used[i]==0 && (i == 0 || used[i-1] ==1 || nums[i]!=nums[i-1])){
List<Integer> copy = new ArrayList<>(list);
copy.add(nums[i]);
int[] usedCopy = Arrays.copyOf(used,used.length);
usedCopy[i] = 1;
dfs(copy,usedCopy,usedCount+1);
}
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode47-%e5%85%a8%e6%8e%92%e5%88%97ii/
