子集问题

一、问题描述

集合{a，b}的子集有{}，{a}，{b}，{a，b}

二、解决问题
问题分析：集合的子集问题在高中就已经见过，一个集合的子集有2ⁿ个。关于为什么是这样的结果呢？我们可以想象一下，一个子集中包含完整集合中的元素，每一个元素在子集中有存在和不存在两种状态，所以子集可能的状态个数就是2x2x...就是2ⁿ个。将子集中的元素对应到bit，0表示元素不存在，1表示元素存在。每一个子集都对应了一个二进制数字，如上问题描述中，{}对应着0b00，{a，b}对应着0b11.

所以可以根据每个子集对应着的数字来计算子集，C++代码如下

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int total = 1 << nums.size();
        vector<vector<int>> res(total);
        for(int i = 0; i < total; i++){
            for(int j = i, k = 0; j; j >>= 1, ++k){
                if(j & 0x1){
                    res[i].push_back(nums[k]);
                }
            }
        }
        return res;
    }
};