6ms C++ iterative solution


  • 0
    B

    Sort first, use cnt to track how many duplicated numbers that is.
    e.g. [2, 2, 2]
    The first 2 is the 3rd duplicated number. Get the result of the last [2, 2] and store it in ret, whose size is s.
    Duplicate the last s / cnt elements in ret, and push back the first 2 to them.

    vector<vector<int>> subsetsWithDup(vector<int>& nums)
    {
        int cnt = 1;
        sort(nums.begin(), nums.end());
        return helper(nums, cnt);
    }
    
    vector<vector<int>> helper(vector<int>& nums, int& cnt)
    {
        vector<vector<int>> ret;
        if(nums.size() == 0) return {{}};
        
        int tmp = nums[0];
        nums.erase(nums.begin());
        
        int flag = nums.size() != 0 && tmp == nums[0] ? true : false;
        ret = helper(nums, cnt);
        if(flag) cnt++;
        else cnt = 1;
        
        int s = ret.size();
        int multi = s / cnt;  //Divide the same cnt times.
        for(int i = s - multi; i < s; ++i)
        {
            ret.push_back(ret[i]);     //Duplicate in the back and push back tmp.
            ret.back().push_back(tmp);
        }
        return ret;
    }

Log in to reply
 

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