跳转至

78 子集

迭代法

用二进制表示每个幂集,第i位为1表示选择第i个元素,那么总共有2^n - 1个状态

class Solution {
private:
    vector<int> t;
    vector<vector<int>> ans;
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        // 总共有2^n - 1种状态
        for(int mask = 0; mask < (1 << n); mask++){
            // 每个状态对应的序列不同
            t.clear();
            // 枚举每个元素
            for(int i = 0; i < n; i++){
                // 1 << i表示第i位为1
                // mask & (1 << i)表示mask状态第i位为1
                // 即选择第i个元素
                if(mask & (1 << i)){
                    t.push_back(nums[i]);
                }
            }
            ans.push_back(t);
        }
        return ans;
    }
};

递归法

用idx记录当前遍历到第几个元素,分类讨论:

  • 选择当前元素,如果选择当前元素,那么dfs之后需要回溯
  • 不选择当前元素
class Solution {
private:
    vector<vector<int>> ans;
    vector<int> res;
    void dfs(vector<int>&nums, int idx){
        if(idx == nums.size()){
            ans.push_back(res);
            return;
        }
        res.push_back(nums[idx]);
        dfs(nums, idx + 1);
        res.pop_back();
        dfs(nums, idx + 1);
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};