给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]输出:[  [1,1,2],  [1,2,1],  [2,1,1]] 思路和上一题类似，知识这里要判断当前元素是否在前面出现过

1 class Solution { 2 public: 3    bool contain(vector
     
      nums, int i, int j){ 4        for(int k = i; k < j; k++) 5            if(nums[j] == nums[k]) return true; 6        return false; 7    } 8     void permuteUnique(vector
      
       &nums, vector
       
        
         >& ans, int begin, int end){ 9         if(begin == end){10             ans.push_back(nums);11             return;12         }else{13             for(int i = begin; i <= end; i++){14                 if(contain(nums, begin, i)) continue;15                 swap(nums, begin, i);16                 permuteUnique(nums, ans, begin+1, end);17                 swap(nums, begin, i);18             }19         }20     }21     22     void swap(vector
         
          & nums, int i, int k){23         int temp = nums[i];24         nums[i] = nums[k];25         nums[k] = temp;26     }27     28     vector
          
           
            > permuteUnique(vector
            
             & nums) {29 vector
             
              
               > ans;30 int len = nums.size()-1;31 permuteUnique(nums, ans, 0, len);32 return ans;33 }34 };
              
             
            
           
          
         
        
       
      
     

 

发现一种更优的解法， 就是在传递nums的时候不用引用，这样就只需要一次交换。判断是否是重复元素也方便很多

此外在调用函数前要先对nums进行排序

1 class Solution { 2 public: 3     void permuteUnique(vector
     
      nums, vector
      
       
        >& ans, int begin, int end){ 4         if(begin == end){ 5             ans.push_back(nums); 6             return; 7         }else{ 8             for(int i = begin; i <= end; i++){ 9                 if(i > begin&&nums[i]==nums[begin]) continue;10                 swap(nums[begin], nums[i]);11                 permuteUnique(nums, ans, begin+1, end);12             }13         }14     }15     16     vector
        
         
          > permuteUnique(vector
          
           & nums) {17 vector
           
            
             > ans;18 int len = nums.size()-1;19 sort(nums.begin(), nums.end());20 permuteUnique(nums, ans, 0, len);21 return ans;22 }23 };