子集
- 难度： 中等
- 通过率： 49.6%
- 题目链接：https://leetcode-cn.com/problems/subsets
题目描述
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
解法一：迭代
考虑数组 [1,2,3]，从左到右来遍历数组，初始结果中只包含一个空集：
[]
现在有了数字 1，可以得到子集（加入空行，以区分原来的子集和新增的子集）：
[]
[1]
加入数字 2 以后，得：
[]
[1]
[2]
[1,2]
数字 3 到来后，得到：
[]
[1]
[2]
[1,2]
[3]
[1,3]
[2,3]
[1,2,3]
可以看到，每新增一个数，产生的子集就是把之前的子集中都加入当前数字。
由此，可以写出如下代码：
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
result.reserve(pow(2, nums.size()));
result.push_back(vector<int>());
for(int n: nums){
int len = result.size();
for(int i=0; i<len; i++){
vector<int> subset = result[i];
subset.push_back(n);
result.push_back(::move(subset));
}
}
return result;
}
};
解法二：位图
子集，实际上就是考虑每个数字是否出现在集合中。一个数出现与不出现共两种情况，因此 n 个数的子集共有 2^n 个。把这 n 个数对应到 n 位二进制上，每个数出现与否体现为二进制位为 0 或 1。因此，在 [0,2^n) 之间的每一个数的二进制信息就能唯一确定一个子集。
比如对于集合 [1,2,3], 001 就表示只取第 1 个元素，构成集合为 {1}。101 就表示只取 1 和 3，表集合 {1,3}。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
unsigned int len = pow(2, nums.size());
for(unsigned int i = 0; i < len; i++){
vector<int> subset;
unsigned int n = i;
for(int j=0; n != 0; j++){
if(n & 1){
subset.push_back(nums[j]);
}
n >>= 1;
}
result.push_back(::move(subset));
}
return result;
}
};
当待求子集的集合长度不大于 32 的时候，可以使用 int 来记录子集的总数量，当大于 32 的时候，可以使用 64 位整数，不过就算 32 位，也已经非常大了。