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],
[]
]
由于元素中可能存在重復，因此較之于Subset的實現，需要加一些判斷。如果碰到了重復元素，只需要在上一次迭代新增的子集的基礎上再進行迭代即可。實現代碼如下：
1 public class SubsetsII {
2 public ArrayList<ArrayList<Integer>> subsetsWithDup(
int[] num) {
3 ArrayList<ArrayList<Integer>> ret =
new ArrayList<ArrayList<Integer>>();
4 ArrayList<ArrayList<Integer>> lastLevel =
null;
5 ret.add(
new ArrayList<Integer>());
6 Arrays.sort(num);
7 for (
int i = 0; i < num.length; i++) {
8 ArrayList<ArrayList<Integer>> tmp =
new ArrayList<ArrayList<Integer>>();
9 ArrayList<ArrayList<Integer>> prev = i == 0 || num[i] != num[i - 1] ? ret : lastLevel;
10 for (ArrayList<Integer> s : prev) {
11 ArrayList<Integer> newSet =
new ArrayList<Integer>(s);
12 newSet.add(num[i]);
13 tmp.add(newSet);
14 }
15 ret.addAll(tmp);
16 lastLevel = tmp;
17 }
18 return ret;
19 }
20 }