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
2
3
4
5
| [
[1,1,2],
[1,2,1],
[2,1,1]
]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
if(nums.length == 0){
return ans;
}
ArrayList<Integer> t = new ArrayList<Integer>();
boolean[] used = new boolean[nums.length];
dfs(nums, ans, t, used);
return ans;
}
public void dfs(int[] nums, List<List<Integer>> ans, ArrayList<Integer> t, boolean[] used){
if(t.size() == nums.length){
ans.add(new ArrayList<Integer>(t));
return ;
}
else{
for(int i=0; i<nums.length; i++){
if(!used[i]){
if(i>0 && nums[i] == nums[i-1] && used[i-1]) continue;
used[i] = true;
t.add(nums[i]);
dfs(nums, ans, t, used);
used[i] = false;
t.remove(t.size()-1);
}
}
}
}
}
|
if(i>0 && nums[i] == nums[i-1] && used[i-1]) continue; Notice this is i-1， not i- also, when adding terms to ans, you should new a ArrayList
- Using Dfs, remenber to remove the character you just processed.
