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]
]
public class Solution {
private List<List<Integer>> ans = new ArrayList<List<Integer>>();
private Set<ArrayList<Integer>> currentSet = new HashSet<ArrayList<Integer>>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
// List<Integer> result = new ArrayList<Integer>();
if(nums.length<=0||nums == null)
return ans;
dfs(0,nums);
ans = new ArrayList<List<Integer>>(currentSet);
return ans;
}
void dfs(int start,int[] nums)
{
if(start == nums.length)
{
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int i=0;i<nums.length;i++)
temp.add(nums[i]);
currentSet.add(temp);
// ans.add(temp);
}
else
{
for(int j=start;j<nums.length;j++)
{
if(j!=start&&nums[j]==nums[j-1])
continue;
int temp1 = nums[start];
nums[start] = nums[j];
nums[j] = temp1;
dfs(start+1,nums);
int temp2 = nums[start];
nums[start] = nums[j];
nums[j] = temp2;
}
}
}
}
