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

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

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) {
        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;
    }
};

Mistakes:
1: copyArrayList()加了start 参数后，在函数里面，忘了把从0开始，改成从start开始。

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

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

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
        Arrays.sort(S);
       ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        all.add(new ArrayList<Integer>());
        for(int i=0;i<S.length;i++){
            int newVal = S[i];
            int count =1;
            while(i+1<S.length && S[i+1] == S[i]){
                i++;
                count++;
            }
            int origLength = all.size();
            for(int j = 0; j< origLength;j++   ){ // for each original all  of 
                for(int len = 1; len<=count; len++ ){ // for each permutation of sequencial "333"
                // add len number of ewVal at the end of newAll
                    ArrayList<Integer> newAll = new ArrayList<Integer>(all.get(j));
                    for(int k =0; k< len; k++)
                        newAll.add(newVal);   
                    all.add(newAll);
                }
            } // end of for loop for each line of all
        } // end of for loop for each S[i]
        return all;
    }
}

---------------------- 3 rd ------------非要用 递归，结果超过30行了--------------------

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
        Arrays.sort(S);
        return subsets(S, 0);
    }

    private ArrayList<ArrayList<Integer>> subsets(int[] S, int start) {
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        if (start == S.length) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            all.add(al);
            return all;
        }
        int count = 1;
        // find till the next one
        while (start < S.length - 1 && S[start] == S[start + 1]) {
            count++;
            start++;
        }
        ArrayList<ArrayList<Integer>> lastAll = subsets(S, start + 1);
        for (int j = 1; j <= count; j++)
            all.addAll(copyAndAdd(lastAll, S[start],j));
        all.addAll(lastAll);
        return all;
    }

    private ArrayList<ArrayList<Integer>> copyAndAdd(
            ArrayList<ArrayList<Integer>> all, int val,int count) {
        ArrayList<ArrayList<Integer>> newAll = new ArrayList<ArrayList<Integer>>();
        for (ArrayList<Integer> al : all) {
            ArrayList<Integer> newAl = new ArrayList<Integer>();
            for (int i = 0; i < al.size(); i++)
                newAl.add(al.get(i));
            for(int i =0;i<count;i++)
                newAl.add(0, val);
            newAll.add(newAl);
        }
        return newAll;
    }
}