90. Subsets II

90. Subsets II

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ret;
        ret.push_back({});
        sort(nums.begin(), nums.end()); // 把重复的放到一起
        int i = 0;
        while(i < nums.size())
        {
            int count = 1;
            while(count + i < nums.size() && nums[i] == nums[count + i])  // 记录重复的数字，对于一个i开始，如果i+count处的值和i一样，那么++
                ++count;
            int n = ret.size(); // 获得ret中的元素个数
            for(int j = 0; j < n; ++j) // 依次从ret中取出所有的列，为了给他们结尾增加
            {
                auto tmp = ret[j];
                for(int k = 0; k < count; ++k)
                {
                    tmp.push_back(nums[i]); // 对于重复的个数，每种个数添加一次防止重复
                    ret.push_back(tmp);
                }
            }
            i += count; // 跳到没有重复的位置
        }
        return ret;
    }
};

DFS

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        backTrack(ret, nums, {}, 0);
        return ret;
    }
private:
    void backTrack(vector<vector<int>>& ret, vector<int>& nums, vector<int> tmp, int start)
    {
        ret.push_back(tmp);
        for(int i = start; i < nums.size(); ++i)
        {
            // 补，如果在这层回溯你用了这个数字后，这层你就别想再用这个数字了，而这层也代表结果中的每个位。
            if(i != start && i > 0 && nums[i] == nums[i - 1]) // 对于重复的每个位置，都只添加一次，绝不添加多次重复部分的多个位置
                continue;
            tmp.push_back(nums[i]);
            backTrack(ret, nums, tmp, i + 1);
            tmp.pop_back();
        }
    }
};