Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
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; }} |
原文：http://www.cnblogs.com/averillzheng/p/3537230.html