原题
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [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/