8ms C++ solution, easy to understand


  • 0
    W

    The idea is to first remove the duplicates (keeping record of the number of duplicates) and then perform a DFS. For example, for nums = [5, 6, 6], we first remove the duplicates and get sinNums = [5, 6], dups = [1, 2] (meaning that 5 appears once and 6 appears twice). After that, the following DFS is performed:

    path = [] -> [5] -> [5, 6] -> [5, 6, 6] -> [6] -> [6, 6]

    class Solution {
    public:
        vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            if (nums.size() == 0)
                return vector<vector<int>>();
            vector<int> path;
            vector<vector<int>> res(1, path);
            sort(nums.begin(), nums.end());
            vector<int> sinNums(1, nums[0]), dups(1, 1);
            for (int i = 1; i < nums.size(); i++)
                if (nums[i] != nums[i - 1])
                    sinNums.push_back(nums[i]), dups.push_back(1);
                else
                    dups[dups.size() - 1]++;
            __subsetsWithDup(sinNums, dups, res, path, 0);
            return res;
        }
        
    private:
        void __subsetsWithDup(vector<int>& nums, vector<int>& dups, vector<vector<int>>& res, vector<int>& path, int pos) {
            for (int j = pos; j < nums.size(); j++) {
                int count = 0;
                for (int i = 0; i < dups[j]; i++) {
                    path.push_back(nums[j]);
                    res.push_back(path);
                    __subsetsWithDup(nums, dups, res, path, j + 1);
                    count++;
                }
                path.erase(path.end() - count, path.end());
            }
            return ;
        }
    };

Log in to reply
 

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