Three typical solutions to handle it in C++


  • 1

    Bit manipulation

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

    Backtracking method

    class Solution {
    private:
        int size;
        void collect(vector<int>& nums, int pos, vector<int>& v, vector<vector<int>>& vv)
        {
            vv.push_back(v);
            for(int i = pos; i < size; ++i)
            {
                v.push_back(nums[i]);
                collect(nums, i+1, v, vv);
                v.pop_back();
            }
        }
    public:
        vector<vector<int>> subsets(vector<int>& nums) 
        {
            size = nums.size();
            vector<int> v;
            vector<vector<int>> vv;
            collect(nums, 0, v, vv);
            return vv;
        }
    };
    

    So-called DP way

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) 
        {
            vector<vector<int>> vv0, vv;
            vv.push_back(vector<int>());
            for(int i = 0; i < nums.size(); ++i)
            {
                vv0 = vv;
                for(auto& subset: vv0) subset.push_back(nums[i]);
                vv.insert(vv.end(), vv0.begin(), vv0.end());
            }
            return vv;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.