90. Subsets II ---------M ~~~~~~~

Given an integer array nums that may contain duplicates, return all possible  (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
 
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
 
Constraints:
1 <= nums.length <= 10
-10 <= nums[i] <= 10

A:
之前的思路，很僵化，迂腐。 还是局限于问题I， 先找到，然后消除重复。
但，实际上，我们可以对重复的元素，多进行分析。得到如下 方法。
先sort（ S) , ，then for each distinct value in S, say  val,  we find different sets of  permutation of val,
if val is single valued, it has only one permutation
if val has multiple value, we generate them and adding on back separately.
for example, val is S = [1 ,2,2], when adding value 2, we first generate all permutation of [2,2],

class Solution {

public:

vector<vector<int>> subsetsWithDup(vector<int>& nums) {

vector<vector<int>> res{{}};

sort(nums.begin(), nums.end());

int start=0;

while(start< nums.size()){

int preSize = res.size();

int count = 1; // count of value of nums[i]

while(start+count < nums.size() && nums[count +start] == nums[start]){

count++;

}

for(int c = 1; c<= count; c++){ //push multiple of same value based on same preSize

for(int t =0; t < preSize; t++){

auto line = res[t];

vector<int> tmp = line;

for(int k = 0; k<c; k++) // push multiple of same value

tmp.push_back(nums[start]);

res.push_back(tmp);

}

}

start+= count;

}

return res;

}

};

之前的实现。 使用了map来count  

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        unordered_map<int,int> map;
        for(auto v:nums)
            map[v] += 1;
        
        vector<vector<int>> res{vector<int>()};
        auto iter = map.begin();
        while(iter != map.end()){
            int curSubsetSize = res.size();
            for(int k =1;k<=iter->second;k++){ // for how many time, we append this new value
                for(int i =0;i<curSubsetSize;i++){
                    vector<int> newLine(res[i]);
                    for(int j = 0;j<k;j++)
                        newLine.push_back(iter->first);
                    res.push_back(newLine);
                }
            }
            iter++;
        }
        return res;
    }
};

Learned:
中心思想就是，把相同的数字，当做一组来看待。然后，循环加入。

----------------第二遍，  思路同上-- 只不过， 因为对new ArrayList<Integer>(al) 命令，给出的是一个新的对象，而不是像all那样，是一个引用。 所以，我们可以节省一些空间。