Non recursive concise solution with comments in code, no triple loops


  • 0
    Q
    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            
            vector< vector<int> > res;
            res.push_back( vector<int>() );
            
            sort(nums.begin(), nums.end());
            
            //nCurr: the number of entries added to res when processing nums[i];
            //nPrev: the number of entries added to res when processing nums[i-1];
            int nCurr=0, nPrev=0;
            
            for(int i=0; i<nums.size(); i++)
            {
        
                int nSize=res.size();
                nCurr=0;
                
                for(int j=0;j<nSize; j++)
                {
                    //skip the entries that were not added when processing nums[i-1];
                    if(i>0 && nums[i]==nums[i-1] && j<nSize-nPrev ) 
                        continue;
                    
                    res.push_back( res[j] );
                    res.back().push_back(nums[i]);
                    
                    nCurr++;
                }
                nPrev=nCurr;
            }
            
            return res;
        }
    };

Log in to reply
 

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