原文链接
题目
给定一个集合，输出其所有子集
例子
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
思路一
设最终子集集合为res，初始从空集出发。对nums中的数进行遍历,每个在各子集中状态只有两种，“出现”或“不出现”，要输出所有子集，则每种状态都要有。未遍历到第i个数时，所有子集中都没出现该数，对所有现有子集进行遍历，加上该数，形成新子集，加入res中。其python代码比较简洁，如下
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for i in nums:
res = res + [[i] + num for num in res]
return res
思路二
个人认为总体思路相近，不过比较巧妙。运用了正交试验设计的思想。从例子可以看出,若nums中有N个数，则子集将有2N个，因为每个数都有“出现”和“不出现”两种状态。那不如一开始就把这2N个子集置为空，然后依次根据状态往里填数据。步骤如下：
- 对nums中第一个数，每隔2^0个数切换一次状态，即第一个子集中出现，第二个子集不出现，第三个出现……
- 对nums中第二个数，每隔2^1个数切换一次状态，即第一、二个子集中出现，第三、四个子集中不出现……
- 对nums中第三个数，每隔2^2个数切换一次状态……
这样最终结果也一定是完整的子集，C++代码如下。
vector<vector<int>> subsets(vector<int> &nums)
{
int S = nums.size();
int resS = 1 << S;
vector<vector<int>> res(resS, vector<int>());
for (int j =0; j < S; ++j)
{
for (int i = 0; i < resS; ++i)
{
if((i >> j) & 1)
{
res[i].push_back(nums[j]);
}
}
}
return res;
}
