力扣_数组28—子集

题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输入： n u m s = [ 1 , 2 , 3 ] nums = [1,2,3] nums=[1,2,3]
输出： [ [ ] , [ 1 ] , [ 2 ] , [ 1 , 2 ] , [ 3 ] , [ 1 , 3 ] , [ 2 , 3 ] , [ 1 , 2 , 3 ] ] [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

思路

  • 回溯
  • n u m s nums nums 中每一位选或者不选，构成了所有的子集，共 2 n 2^n 2n 种
    • 每一位选或者不选可以用 0 , 1 0,1 0,1 表示
    • 0~ 2 n − 1 2^n-1 2n−1 对应的二进制数对应了所有可能的子集
    • 如假设数组长度为 6 6 6， 001101 001101 001101 表示 选择第 0 , 2 , 3 0,2,3 0,2,3 个数，其他不选

代码

class Solution {
public:
    // void subfind(vector<int>& nums, vector<int>& vec, vector<vector<int>>& ret, int max_len, int ind){
    //     if(vec.size() == max_len){
    //         ret.push_back(vec);
    //         return;
    //     }
    //     for(int i = ind; i < nums.size(); i++){
    //         vec.push_back(nums[i]);
    //         subfind(nums, vec, ret, max_len, i+1);
    //         vec.pop_back();
    //     }
    // }
    // vector<vector<int>> subsets(vector<int>& nums) {
    //     int n = nums.size();
    //     vector<int> vec;
    //     vector<vector<int>> ret;
    //     for(int i = 0; i <= n; i++){
    //         subfind(nums, vec, ret, i, 0);
    //     }
    //     return ret;
    // }

    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ret;
        int mask_max = pow(2, n);
        for(int mask = 0; mask < mask_max; mask++){
            vector<int> vec;
            for(int i = 0; i < n; i++){
                if(mask & 1 << i){
                    vec.push_back(nums[i]);
                }
            }
            ret.push_back(vec);
        }
        return ret;
    }
};