Leetcode-78. 子集

78. 子集

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

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

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

1 <= nums.length <= 10-10 <= nums[i] <= 10nums 中的所有元素 互不相同

由于数组的长度最长为10，因此我们可以用一个最大为2^10的二进制数表示每一位是取还是不取，1表示取，0表示取，如nums={1,3,2,6}来说，mask = 3 ->0011表示取{2,6}，mask=8->1000表示取{1}，以此类推，我们只要遍历所有情况，将其取出即可。

class Solution {
public:
    vector> subsets(vector& nums) {
        vector cur;
        vector> res;
        int n=nums.size();
        for(int i=0; i < (1<> j) & 1) == 1 ) cur.push_back(nums[j]);
            }
            res.push_back(cur);
        }
        return res;

    }
};

dfs,考虑每个位置选择和不选择两种情况，直到考虑完所有位置。

class Solution {
public:
    vector cur;
    vector> res;
    void dfs(int index, vector& cur, vector& nums){

        if(index==nums.size()) {res.push_back(cur); return;}
        cur.push_back(nums[index]);
        dfs(index+1,cur,nums);
        cur.pop_back();
        dfs(index+1,cur,nums);
    }
    vector> subsets(vector& nums) {
        dfs(0, cur, nums);
        return res;
    }
};

Leetcode-2044. 统计按位或能得到最大值的子集数目