Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Leetcode:Permutations II
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
34
35
36
37
38
39
40
41
42
43
public class Test {
static ArrayList<Integer> arrayList = new ArrayList();
static HashSet<Integer> set = new HashSet<>();
static ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<ArrayList<Integer>>();
public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
Arrays.sort(num);
combination(num, 0);
return arrayLists;
}
public static void main(String[] args) {
permuteUnique(new int[]{1, 1, 2});
System.out.println(arrayLists);
}
public static void combination(int[] num, int index) {
if (arrayList.size() < num.length) {
for (int i = 0; i < num.length; i++) {
//把相同的第一个加入进去,只能以一种顺序加入进去.这里用的逆序,也就是收第二个1和第一个1,第3个2这样的顺序
if (set.contains(i)||(i-1>=0&&(num[i]==num[i-1])&&set.contains(i-1))) {
continue;
}
//存储下标
set.add(i);
arrayList.add(num[i]);
combination(num, i);
}
} else {
ArrayList<Integer> templist = new ArrayList(arrayList);
arrayLists.add(templist);
}
if (arrayList.size() > 0) {
arrayList.remove(arrayList.size() - 1);
set.remove(index);
}
}
}
