Recursive only to semi recurive with comments


  • 2
    L
    // bottom up,build from [], and add to result on the way , 
    // add elements one by one in the existing subset cur,  
    // then what has been added, do not use it again.
    void subs2(vector<int> &nums, vector<int> &cur, int i=0)
    {
        res.push_back(cur);
        
        for( ;i<nums.size();i++)
        {
            cur.push_back(nums[i]);
            subs2(nums,cur, i+1);
            cur.erase(cur.end()-1);
        }
        
    }
    
    //choice based, top down, build along the way, and add in the end;
    void subs(vector<int> &nums, int i, vector<int> &cur)
    {
        
        if( i == nums.size())
        {
            res.push_back(cur);
            return;
        }
        //skip ith
        subs(nums,i+1,cur);
        // pick ith, i+1 ensures that same element does not reappear in the same subset. 
        cur.push_back(nums[i]);
        subs(nums,i+1,cur);
        cur.erase(cur.end()-1);
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        
        vector<int> cur;
       sort(nums.begin(),nums.end());
        subs2(nums,cur,0);
        return res;
        
    }

Log in to reply
 

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