Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations:
[ [1,1,2], [1,2,1], [2,1,1] ]
代码如下：
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class PermutationIIContainsDuplication { public List<ArrayList<Integer>> permutationII(int[] nums){ List<ArrayList<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list,new ArrayList<>(),nums,new boolean[nums.length]); return list; } private void backtrack(List<ArrayList<Integer>> list, ArrayList<Integer> arrayList, int[] nums, boolean[] used) { if(arrayList.size() == nums.length) list.add(new ArrayList<>(arrayList)); else{ for(int i=0;i<nums.length;i++){ if(used[i] || i>0&&nums[i]==nums[i-1]&&!used[i]) //避免出现重复结果 continue; used[i]=true; arrayList.add(nums[i]); backtrack(list,arrayList,nums,used); used[i]=false; arrayList.remove(arrayList.size()-1); } } } }