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].

1 我的思路，在Permutations的基础上对结构去重，不过超时了。。

class Solution {        vector
     
      
        > m_result;    public:        void swap(int & x, int & y)        {            int tmp = x;            x = y;            y = tmp;        }        void dfs(vector
       
         & num, int dep )        {            if(dep == num.size())            {                m_result.push_back(num);                return;            }               for(int i = dep; i < num.size(); i++)            {                       //if(i != dep && num[i] == num[dep])                    //    continue;                    swap(num[i], num[dep]);                    dfs(num, dep + 1);                     swap(num[i], num[dep]);            }           }               vector
        
         
           > permuteUnique(vector
          
            &num) { dfs( num, 0); //erase the duplicate sort(m_result.begin(), m_result.end()); m_result.erase(unique(m_result.begin(), m_result.end()), m_result.end()); return m_result; }};
          
         
        
       
      
     

思路2 copy from  

先对数组进行排序，这样在DFS的时候，可以先判断前面的一个数是否和自己相等，相等的时候则前面的数必须使用了，自己才能使用，这样就不会产生重复的排列了。

解释：假设有相同的3个2，排序后按照顺序称为2a,2b,2c, 由于保证前面数使用后，后面的数才能有，保证了最后的结果中2a在2b之前，2b在2c之前，这样就避免了重复。

 

class Solution {private:    bool canUse[100];    int a[100];    vector
     
      
        > ret;public:    void dfs(int dep, int maxDep, vector
       
         &num)    {        if (dep == maxDep)        {            vector
        
          ans;            for(int i = 0; i < maxDep; i++)                ans.push_back(a[i]);            ret.push_back(ans);            return;        }                for(int i = 0; i < maxDep; i++)            if (canUse[i])            {                if (i != 0 && num[i] == num[i-1] && canUse[i-1])                    continue;                                    canUse[i] = false;                a[dep] = num[i];                dfs(dep + 1, maxDep, num);                canUse[i] = true;            }    }        vector
         
          
            > permuteUnique(vector
           
             &num) { // Start typing your C/C++ solution below // DO NOT write int main() function sort(num.begin(), num.end()); memset(canUse, true, sizeof(canUse)); ret.clear(); dfs(0, num.size(), num); return ret; }};