学步园

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have
the following unique permutations:

[1,1,2], [1,2,1],
and [2,1,1].

思路：这道题可以用递归的方式求解，先获得所有的数字（唯一的），然后统计这些数字的频次，递归中判断频次是否大于0，是则为位置Pos的值，不是

则获得下一个数字。

class Solution {
private:
    vector<int> f;
    map<int,int> unique;
    vector<vector<int> > res;
public:
    void permuteUnique(int n, int k) {
        if (k == n)
        {
            res.push_back(f);
        }       
        else {
            map<int,int>::iterator it;
            for(it=unique.begin(); it!=unique.end(); ++it)
            {
                if(it->second > 0) 
                {
                    it->second--;
                    f[k] = it->first;
                    permuteUnique(n,k+1);
                    it->second++;
                }    
            }    
        }    
    }    
    vector<vector<int> > permuteUnique(vector<int> &num) 
    {
        if(num.empty()) {
            return res;
        }    
        int len = num.size();
        f.resize(len);
        int i,j;
        for(i=0; i<len; ++i)
        {
            if(unique.find(num[i]) != unique.end())
            {
                unique[num[i]]++;
            }    
            else 
            {
                unique.insert(pair<int,int>(num[i],1));
            }    
        }    
        permuteUnique(len,0);          
        return res;
  }    
};