90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

先将数组排序，在回溯的过程中，去除重复的元素

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> subset;
        vector<vector<int>> subsets;
        sort(nums.begin(), nums.end());
        genSubset(nums, 0, subset, subsets);
        return subsets;
    }
private:
    void genSubset(vector<int>  &arr, int level, vector<int> &subset, vector<vector<int>> &res){

        res.push_back(subset);

        for(int i = level; i < arr.size(); i++){
            subset.push_back(arr[i]);
            genSubset(arr, i + 1, subset, res);
            subset.pop_back();
            int j = i + 1;
            //跳过重复的数字
            while(arr[j] == arr[j - 1] && j <arr.size()){
                j++;
            }
            i = j - 1;
        }
    }
};