LeetCode 78 子集

78.子集

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

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

暴力递归

本题的重点在于问题的划分，假设对于一个数组 nums=[1,2,3] ，那么在问题的划分上应该是：选取 1 作为子集中的元素，那么在后续的处理中，应该求出 包含元素 1 的子集。在找完相应的子集后，再将 2 作为初始子集中的元素，再求出包含 2 中全部的子集（并且不包含1），向后依次类推，那么也就将问题转化为了如何求解包含 i 的数组的全部子集。

使用递归的方式进行求解，每次预先在 tmp 数组中加入 nums[cur] ，然后开始递归 DFS(nums,cur+1) ，选取 cur+1 作为子集的第二个元素，得到一个新的子集，加入到结果数组中，再次递归向下选取第三个元素 DFS(nums,cur+2) ，在递归返回后回溯，选取 cur+2 作为子集的第二个元素。那么递归结束的条件为： cur==nums.size() 。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void DFS(vector<int>& nums,int cur){
        if(cur==nums.size()){
            return;
        }
        for(int i=cur;i<nums.size();i++){
            tmp.push_back(nums[i]);
            res.push_back(tmp); // 得到新的子集
            DFS(nums,i+1); // 递归
            tmp.pop_back(); // 回溯
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        res.push_back({});
        for(int i=0;i<nums.size();i++){
            tmp.clear(); // 清空之后选取新的元素作为子集的首元素
            tmp.push_back(nums[i]);
            res.push_back(tmp);
            DFS(nums,i+1);
        }
        return res;
    }
};

枚举元素是否选取

基本思想为，使用递归函数创建一个子集，让子集成为递归树中的叶子节点，那么在到达叶子节点后，就能够实现选取。在创建子集时序列中的元素仅有两种状态，选取或不选取：

1. 选取当前元素 nums[cur] ，然后 cur+1 向下递归，那么就能够找到包含当前元素的全部子集
2. 不选取当前 nums[cur] ，然后 cur+1 向下递归，那么就能够找到不包含当前元素的全部子集
3. 递归结束的条件： cur=nums.size() 此时将会到达叶节点

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void DFS(vector<int>& nums,int cur){
        if(cur==nums.size()){
            res.push_back(tmp);
            return;
        }
        tmp.push_back(nums[cur]);
        DFS(nums,cur+1);
        tmp.pop_back();
        DFS(nums,cur+1);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        DFS(nums,0);
        return res;
    }
};

基于迭代法进行元素的枚举

对于包含n个元素的集合，构建他的全部子集，对于每一个元素而言只有选和不选两种状态，因此总计 $2^n$ 个状态，使用一个n位的二进制数即可描述。因此只要构造 0/1 序列，按照 0/1 序列在原集合当中取数即可完成穷举。

首先是总体数据的循环控制： $0-2^n-1$ 内进行循环， mask 代表选取元素的二进制序列，从0开始，要是实现元素的选取就需要判断 mask 的每一位， mask 总计n位，因此内层循环n次。

逐位判断的实现：判断某个数的第i+1位是0/1，使用与运算实现

mask & (1 << i);// 将1右移i位，转变为第i+1位为1，其他位都为0的二进制数，与运算后的值0/1表示了结果

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;

    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        for (int mask = 0; mask < (1 << n); ++mask) {  // 总体的循环控制
            t.clear();
            for (int i = 0; i < n; ++i) { // 从数组的n个元素中进行选取
                if (mask & (1 << i)) {    // 实现逐位的0/1判断
                    t.push_back(nums[i]);
                }
            }
            ans.push_back(t);
        }
        return ans;
    }
};