題意

給定一組不含重復(fù)元素的整數(shù)數(shù)組nums，返回該數(shù)組所有可能的子集（冪集）。
說明：解集不能包含重復(fù)的子集。
示例:
輸入:nums = [1,2,3]
輸出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

思路

首先因?yàn)轭}目說不含重復(fù)元素，那么可以知道子集總數(shù)為C(0, n) + C(1, n) + ... + C(n, n) = 2^n

于是很自然可以想到二進(jìn)制的全排列，哪一位出現(xiàn)1，則表示該位置數(shù)字被選中，例如樣例中的三個(gè)數(shù)字那么二進(jìn)制全排列為：
000 = [ ]
001 = [ 1 ]
010 = [ 2 ]
011 = [ [1, 2] ]
100 = [ 3 ]
101 = [ [3, 1] ]
...

所以可以根據(jù)這個(gè)進(jìn)行枚舉0~2^n，然后對(duì)每個(gè)數(shù)字進(jì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;
        }
    }
};