leetcode(90) subsets ii 解法

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

解法

时间复杂度为O(2^n)次方,因为最多可能有2^n次方种可能的组合,所以遍历2^n次方次,每次根据对应2进制数的i位确定是否选取第i位的数,注意,list判断重复需要进行排序后再判断

具体代码如下:

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
class  {
public List<List<Integer>> subsetsWithDup(int[] nums) {
HashSet<List<Integer>> hs = new HashSet<>();
int len = nums.length;
int x = (int) (Math.pow(2, len));
for (int i = 0; i < x; i++) {
List<Integer> tmp = new ArrayList<>();
for (int j = i, k = 0; j >= 1; j = j / 2, k++) {
if (j % 2 != 0) {
tmp.add(nums[k]);
}
}
Collections.sort(tmp);
if (!hs.contains(tmp)) {
hs.add(tmp);
}
}
List<List<Integer>> res = new ArrayList<>();
for (List<Integer> item :
hs) {
res.add(item);
}
return res;
}
}