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

 

这道题是之前那道的延伸，由于输入数组有可能出现重复数字，如果按照之前的算法运算，会有重复排列产生，我们要避免重复的产生，在递归函数中要判断前面一个数和当前的数是否相等，如果相等，前面的数必须已经使用了，即对应的visited中的值为1，当前的数字才能使用，否则需要跳过，这样就不会产生重复排列了，代码如下：

 

解法一：

class Solution {public:    vector
     
      
        > permuteUnique(vector
       
         &num) {        vector
        
         
           > res;        vector
          
            out; vector
           
             visited(num.size(), 0); sort(num.begin(), num.end()); permuteUniqueDFS(num, 0, visited, out, res); return res; } void permuteUniqueDFS(vector
            
              &num, int level, vector
             
               &visited, vector
              
                &out, vector
               
                
                  > &res) { if (level >= num.size()) res.push_back(out); else { for (int i = 0; i < num.size(); ++i) { if (visited[i] == 0) { if (i > 0 && num[i] == num[i - 1] && visited[i - 1] == 0) continue; visited[i] = 1; out.push_back(num[i]); permuteUniqueDFS(num, level + 1, visited, out, res); out.pop_back(); visited[i] = 0; } } } }};
                
               
              
             
            
           
          
         
        
       
      
     

 

还有一种比较简便的方法，在的基础上稍加修改，我们用set来保存结果，利用其不会有重复项的特点，然后我们再递归函数中的swap的地方，判断如果i和start不相同，但是nums[i]和nums[start]相同的情况下跳过，继续下一个循环，参见代码如下：

 

解法二：

class Solution {public:    vector
     
      
       > permuteUnique(vector
       
        & nums) {        set
        
         
          > res;        permute(nums, 0, res);        return vector
          
           
            > (res.begin(), res.end()); } void permute(vector
            
              &nums, int start, set
             
              
               > &res) { if (start >= nums.size()) res.insert(nums); for (int i = start; i < nums.size(); ++i) { if (i != start && nums[i] == nums[start]) continue; swap(nums[i], nums[start]); permute(nums, start + 1, res); swap(nums[i], nums[start]); } }};
              
             
            
           
          
         
        
       
      
     

 

类似题目：