6ms C++ with explanation


  • 0
    L

    First, sort the array. Duplicate subset occurs when appending duplicate numbers to other numbers. So if we can append duplicate numbers only to newly constructed subsets (subsets constructed with the same value number in the current loop), there will be no duplicates...(I cannot understand my explanation either, just look at the code. pretty straight forward)

    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            vector<vector<int>> fields;
            if (nums.size() == 0) return fields;
            sort(nums.begin(), nums.end());
            vector<int> empty;
            fields.push_back(empty);
            for (int i = 0; i < nums.size(); ++i) {
                int size = fields.size();
                for (int j = 0; j < size; ++j) {
                    vector<int>temp = fields[j];
                    temp.push_back(nums[i]);
                    fields.push_back(temp);
                }
                while (i+1 < nums.size() && nums[i] == nums[i+1]) {
                    int newSize = fields.size();
                    for (int j = size; j < newSize; ++j) {
                        vector<int>temp = fields[j];
                        temp.push_back(nums[i]);
                        fields.push_back(temp);
                    }
                    size = newSize;
                    ++i;
                }
            }
            return fields;
        }
    };
    

Log in to reply
 

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