Tag: 排列组合

思路

换个方法想问题。
有n个数，每个数是否作为输出用0/1状态来表示，比如[1,2,3]全出现就是(1,1,1) => 7，那n个元素的子数组的生成就是以下过程：[0, 2^n)里的每个数i，看这个数i里第[0,n)位是否为1，若为1则表示nums[i]被选中了，否则不选。
比如[1,2,3]的所有子集:

[               [1, 2, 3]
  [3],        => 0, 0, 1  => 1
  [1],        => 1, 0, 0  => 4
  [2],        => 0, 1, 0  => 2
  [1,2,3],    => 1, 1, 1  => 7
  [1,3],      => 1, 0, 1  => 5
  [2,3],      => 0, 1, 1  => 3
  [1,2],      => 1, 1, 0  => 6
  []          => 0, 0, 0  => 0
]

代码

class Solution {
public:
    vector<int> decodeMask(unsigned int mask, const vector<int>& nums){
        vector<int> result;
        unsigned int tester = 0x1;
        for(unsigned int i=0; i<nums.size(); i++){
            if(mask & tester){
                result.push_back(nums[i]);
            }
            tester <<= 1;
        }
        return result;
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> results;
        const unsigned int MAX_MASK = pow(2, nums.size());
        for(unsigned int mask=0; mask < MAX_MASK; mask++){
            results.push_back(decodeMask(mask, nums));
        }
        return results;
    }
};