捕獲.PNG
這道題和Permutations類似，不同的是吩坝，現(xiàn)在包含了重復(fù)的數(shù)字毒姨，那么思路相同，還是利用dp钉寝，只不過首先進(jìn)行排序弧呐，并且遇到重復(fù)的就略過比如1,1,2。那么要做的排序就只有1和2嵌纲，重復(fù)的那個(gè)1就被略過俘枫。代碼如下
public class permuteUnique {
public static List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res =permute(nums);
return res;
}
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res =new ArrayList<>();
if(nums.length==1){
List<Integer> temp = new ArrayList<>();
temp.add(nums[0]);
res.add(temp);
return res;
}
int[] tempNums = new int[nums.length-1];
int pre=0;
for(int i=0;i<nums.length;i++){
if(i>0 && pre==nums[i]){
continue;
}
pre=nums[i];
for(int j=0;j<tempNums.length;j++){
if(j<i){
tempNums[j]=nums[j];
}else if(j>=i){
tempNums[j]=nums[j+1];
}
}
List<List<Integer>> templ = permute(tempNums);
for(int k=0;k<templ.size();k++){
List<Integer> l = templ.get(k);
l.add(nums[i]);
templ.set(k ,l);
}
res.addAll(templ);
}
return res;
}
}
