Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For
example,
If S = [1,2,2],
a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
The method in this post is a kind of "brute force" method. But it can be accepted by leetcode online judge.
I do not know other smarter methods yet.
|
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
44
45
46
|
public class Solution {
public
ArrayList<ArrayList<Integer> > subsetsWithDup(int[] num){
Arrays.sort(num);
HashMap<Integer, Integer> mult = new
HashMap<Integer, Integer>();
HashMap<Integer, Integer> dist = new
HashMap<Integer, Integer>();
int
l = 0;
for(int
i = 0; i < num.length; ++i){
if(mult.containsKey(num[i])){
int
mu = mult.get(num[i]);
mult.put(num[i], ++mu);
}
else{
mult.put(num[i], 1);
dist.put(l, num[i]);
++l;
}
}
ArrayList<ArrayList<Integer> > result = new
ArrayList<ArrayList<Integer> >();
int
nums = (int)Math.pow(2, l);
for(int
i = 0; i < nums; ++i){
ArrayList<ArrayList<Integer> > list = new
ArrayList<ArrayList<Integer> >();
list.add(new
ArrayList<Integer>());
String binaryreps = Integer.toBinaryString(i);
int
length = binaryreps.length();
for(int
j = 0; j < length; ++j){
ArrayList<ArrayList<Integer> > temp = new
ArrayList<ArrayList<Integer> >();
if(binaryreps.charAt(length - 1
- j) == ‘1‘){
while(!list.isEmpty()){
ArrayList<Integer> aList = list.remove(0);
int
times = mult.get(dist.get(j));
for(int
m = 1; m <= times; ++m){
ArrayList<Integer> newList = new
ArrayList<Integer>();
newList.addAll(aList);
for(int
n = 1; n <= m; ++n)
newList.add(dist.get(j));
temp.add(newList);
}
}
list = temp;
}
}
result.addAll(list);
}
return
result;
}
} |