Leetcode 78 寻找所有子集

原文链接

题目

给定一个集合，输出其所有子集

例子

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个数，则子集将有2^{N个，因为每个数都有“出现”和“不出现”两种状态。那不如一开始就把这2}N个子集置为空，然后依次根据状态往里填数据。步骤如下：

• 对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;
}