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]. http://leetcode.com/onlinejudge#question_47

leetcode_permutations_2.cpp

#include <tr1::unordered_map>

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        int n = num.size();
        vector<vector<int> > ans;
        vector<int> id(n);
        for (int i = 0; i < n; ++i)
            id[i] = i;
        ans.push_back(num);
        map<vector<int>, bool> hash;
        hash[num] = true;
        while (next_permutation(id.begin(), id.end())) {
            vector<int> tmp(n);
            for (int i = 0; i < n; ++i)
                tmp[i] = num[id[i]];
            if (hash.find(tmp) == hash.end()) {
                hash[tmp] = true;
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};