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

[解题思路]

跟 Permutations的解法一样，就是要考虑“去重”。

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

与Permitations的code相比，只加了3行，Line 8，23，24。

[Code]

1:    vector
    
     
       > permuteUnique(vector
      
        &num) {  2:      // Start typing your C/C++ solution below  3:      // DO NOT write int main() function  4:      vector
       
        
          > coll;  5:      vector
         
           solution; 6: if(num.size() ==0) return coll; 7: vector
          
            visited(num.size(), 0); 8: sort(num.begin(), num.end()); 9: GeneratePermute(num, 0, visited, solution, coll); 10: return coll; 11: } 12: void GeneratePermute(vector
           
             & num, int step, vector
            
             & visited, vector
             
              & solution, vector
              
               
                 >& coll) 13: { 14: if(step == num.size()) 15: { 16: coll.push_back(solution); 17: return; 18: } 19: for(int i =0; i< num.size(); i++) 20: { 21: if(visited[i] == 0) 22: { 23: if(i>0 && num[i] == num[i-1] && visited[i-1] ==0) 24: continue; 25: visited[i] = 1; 26: solution.push_back(num[i]); 27: GeneratePermute(num, step+1, visited, solution, coll); 28: solution.pop_back(); 29: visited[i] =0; 30: } 31: } 32: }
               
              
             
            
           
          
         
        
       
      
     
    

[Note]

Line 23: Don't miss “&& visited[i-1] ==0”. Or, the inner recursion will skip using duplicate number.