Leetcode(90) Subsets II

发表于 | 分类于

Description

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 Solution {
    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;
    }
}