子集
[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 2
0 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++) {
//当前位是 1
if ((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;
}