78. 子集

题意

给定一组不含重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入:nums = [1,2,3]
输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

思路

首先因为题目说不含重复元素，那么可以知道子集总数为C(0, n) + C(1, n) + ... + C(n, n) = 2^n

于是很自然可以想到二进制的全排列，哪一位出现1，则表示该位置数字被选中，例如样例中的三个数字那么二进制全排列为：
000 = [ ]
001 = [ 1 ]
010 = [ 2 ]
011 = [ [1, 2] ]
100 = [ 3 ]
101 = [ [3, 1] ]
...

所以可以根据这个进行枚举0~2^n，然后对每个数字进行拆分。代码如下：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        int len = nums.size();
        if(len == 0) return ans;
        int max_num = 1 << len;
        vector<int> tmp_array;
        for (int i=0; i<max_num; i++){
            tmp_array.clear();
            get_now_subset(i, nums, tmp_array);
            ans.push_back(tmp_array);
        }
        return ans;
    }
    void get_now_subset(int now_num, vector<int>& nums, vector<int>& subset){
        int len = nums.size();
        for (int i=0; i<len; i++){
            if (now_num & 1){
                subset.push_back(nums[i]);
            }
            now_num >>= 1;
        }
    }
};