作者：jostree   

题目链接：

题目要求对有重复的数组进行无重全排列。为了保证不重复，类似于全排列算法使用dfs，将第一个数字与后面第一次出现的数字交换即可。例如对于序列1,1,2,2

有如下过程：

1,1,2,2 -> 1,1,2,2 -> 1,1,2,2 -> 1,1,2,2

　　　　　　　　　  -> 1,2,1,2 -> 1,2,1,2

　　　　　　　　　　　　　　　 -> 1,2,2,1

　　　　-> 2,1,1,2 -> 2,1,1,2 -> 2,1,1,2

　　　　　　　　　　　　　　　 -> 2,1,2,1

　　　　　　　　　  -> 2,2,1,1 -> 2,2,1,1

代码中使用set来记录数字是否在前面出现过，如果出现过，则不与第一个数字进行交换。

代码如下：

1 class Solution { 2 public: 3 void swap(int &a, int &b) 4 { 5     int tmp = a; 6     a = b; 7     b = tmp; 8 } 9 void p(vector
      
        &num, vector
       
        
          > &res, int begin) 10 {11     if( begin == num.size() )12     {13         vector
         
           tmp;14         for( int i = 0 ; i < num.size() ; i++ )15         {16             tmp.push_back(num[i]);17         }18         res.push_back(tmp);19     }20     else21     {22         set
          
            used;23         for( int i = begin ; i < num.size() ; i++ )24         {25             if(!used.count(num[i]))26             {27                 used.insert(num[i]);28                 swap(num[i], num[begin]);29                 p(num, res, begin+1);30                 swap(num[i], num[begin]);31             }32         }33     }34 }35 vector
           
            
              > permuteUnique(vector
             
               &num) 36 {37 vector
              
               
                 >res;38 if( num.size() == 0 )39 {40 return res;41 }42 sort(num.begin(), num.end());43 p(num, res, 0);44 return res;45 }46 };