【Leecode】子集⭐⭐

子集

[78]子集I

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例输入

示例 1：

输入：nums = [1, 2, 3]

输出：[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

示例 2：

输入：nums = [0]

输出：[[], [0]]

题解

这道题目考察的是如何获取一个数组的幂集，核心思想是幂运算。

public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> ans = new ArrayList<>();int n = nums.length;for (int i = 0; i < (1 << n); i++) {List<Integer> subset = new ArrayList<>();for (int j = 0; j < n; j++) {if ((i & (1 << j)) != 0) {subset.add(nums[j]);}}ans.add(subset);}return ans;
}

这段代码难点在于第7行的条件判断，不容易想到，下面解释一下：

i 是从 0 到 2^n - 1 的整数，它的二进制表示中每一位对应着一个元素是否包含在子集中。例如：

• i = 0 时，二进制是 000，表示空集（[]）。

• i = 1 时，二进制是 001，表示只包含第 0 个元素（[1]）。

• i = 2 时，二进制是 010，表示只包含第 1 个元素（[2]）。

• i = 3 时，二进制是 011，表示包含第 0 个和第 1 个元素（[1,2]）。

• i = 4时，二进制是 100，表示只包含第二个元素 [3]。

• i = 5时，二进制是 101，表示包含第 0 个和第 2 个元素（[1,3]）。

• i = 6时，二进制是 110，表示包含第 1 个和第 2 个元素（[2,3])。

• i = 7时，二进制是 111，表示包含所有元素 ([1,2,3])

观察上面我们就能看出来，遇到二进制是 1 的情况，就把那个元素加到一个子列表里面。

我们判断i的第j位是不是 1可以用位运算实现：i & (1 << j)) != 0

[90]子集II

题目描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例输入

示例 1：

输入：nums = [1, 2, 2]

输出：[[], [1], [1, 2], [2], [2, 2], [1, 2, 2]]

示例 2：

输入：nums = [0]

输出：[[], [0]]

题解

和上面相比就是增加了对重复元素的检查，如果重复就不要加入最终要返回的列表了。

需要注意的是题目中像[1, 2]和[2, 1]认为是相同的，所以对subset要排个序再检查。

public List<List<Integer>> subsetsWithDup(int[] nums) {List<List<Integer>> ans = new ArrayList<>();int n = nums.length;for (int i = 0; i < (1 << n); i++) {List<Integer> subset = new ArrayList<>();for (int j = 0; j < n; j++) {if ((i & (1 << j)) != 0) {subset.add(nums[j]);}}subset.sort(Comparator.naturalOrder());if (! ans.contains(subset)) {ans.add(subset);}}return ans;
}

但这个方法比较耗时间，可以接着想怎么通过位运算改进他。

比如我们看这个 nums = [1, 2, 2]

1	2	20	0	0		[]
0	0	1		[1]
0	1	0		[2]
0	1	1		[1, 2]
1	0	0		[2]
1	0	1		[2, 1]
1	1	0		[2, 2]
1	1	1		[1, 2, 2]

我们注意到：

[2]这个子集出现了两次，对应的是：

0	1	0		[2]
1	0	0		[2]

[1, 2]这个子集也出现了两次，对应的是：

0	1	1		[1, 2]
1	0	1		[2, 1]

那么怎么去重复呢？

有两种情况：

第一种就是，占据了开头，类似于这种 101

第二种就是，没有占据开头，类似于这种 0100，对应 [2]这个子集

除了第一位，其他位的 1 的前边一定是 0。

所以的话，我们的条件是看出现了重复数字，并且当前位是 1 的前一个的二进位。

public List<List<Integer>> subsetsWithDup(int[] num) {Arrays.sort(num);List<List<Integer>> lists = new ArrayList<>();int subsetNum = 1 << num.length;for (int i = 0; i < subsetNum; i++) {List<Integer> list = new ArrayList<>();boolean illegal = false;for (int j = 0; j < num.length; j++) {//当前位是 1if ((i >> j & 1) == 1) {//当前是重复数字，并且前一位是 0，跳过这种情况if (j > 0 && num[j] == num[j - 1] && (i >> (j - 1) & 1) == 0) {illegal = true;break;} else {list.add(num[j]);}}}if (! illegal) {lists.add(list);}}return lists;}