Subsets II

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

Note:

• Elements in a subset must be in non-descending order.
• 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],
  []
]

//本题重点是判断何时会出现duplicate的情况
//让结果decrease排列很简单，只要sort nums就好
//结果中出现duplicate是因为前一个相同的数字没有取，但下一个取了
//比如数列 x1 x2 x3 y1 z1 
//其中x1 = x2 = x3 != y1 != z1
//如果x1没有取，那么x2也不能取，x3也不能取，否则会出现重复结果。
//如果x1取了，x2可以取也可以不取，如果x2没有取，那么x3也不能取。
//在代码中我们用isLastChosen来表示前一个元素取没取。
//时间复杂度o(2^n)
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> re;
        vector<int> thisRe;
        if(nums.empty() == true){
            return re;
        }
        sort(nums.begin(), nums.end());
        _subsetWithDup(re, thisRe, 0, nums, false);
        return re;
    }

    
    void _subsetWithDup(vector<vector<int>> &re, vector<int> &thisRe, int index, vector<int>& nums, bool isLastChosen){
        size_t len = nums.size();
        if(index == len){
            //finish
            re.push_back(thisRe);
            return ;
        }
        if(index == 0 || nums[index] != nums[index - 1]){
            thisRe.push_back(nums[index]);
            _subsetWithDup(re, thisRe, index + 1, nums, true);
            thisRe.pop_back();
            _subsetWithDup(re, thisRe, index + 1, nums, false);
        }
        else{
            //dup, nums[index] == nums[index - 1]
            if(isLastChosen == true){
                thisRe.push_back(nums[index]);
                _subsetWithDup(re, thisRe, index + 1, nums, true);
                thisRe.pop_back();
            }
            _subsetWithDup(re, thisRe, index + 1, nums, false);
        }
    }
};