题目链接：Permutations II

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的基础上，允许数组中有重复元素。不过思路还是类似，只不过需要跳过重复元素。

1. 递归排列

这是一个排列的问题，首先联想到的就是递归方式。对剩余元素排序，然后每次逐个固定每个没有重复元素到第一位置，然后递归排列剩下的元素。当固定到前面的元素数量等于数组长度的时候，递归终止。

注意一点，由于排序会造成num数组元素的顺序变化，因此调用两次swap(num[i], num[j])并不能恢复到原样，因此需要去掉递归函数参数num前面的引用符合‘&’，这样每次退出内层函数后，num数组的元素顺序回复原样。不过这样空间复杂度变高，时间复杂度变高了。。。

时间复杂度：O(n!)（结果数量）

空间复杂度：O(n!)

 1 class Solution
 2 {
 3 public:
 4     vector
   
     > permuteUnique(vector
    
      &num) 5 { 6 vector
     
       > vvi; 7 permuteUnique(num, 0, vvi); 8 return vvi; 9 } 10 private: 11 void permuteUnique(vector
      
        num, int i, vector
       
         > &vvi) 12 { 13 if(i == num.size()) 14 { 15 vvi.push_back(num); 16 return; 17 } 18 19 sort(num.begin() + i, num.end()); 20 21 for(int j = i; j < num.size(); ) 22 { 23 swap(num[i], num[j]); 24 permuteUnique(num, i + 1, vvi); 25 swap(num[i], num[j]); 26 27 while(++ j < num.size() && num[j] == num[j - 1]); 28 } 29 } 30 };
       
      
     
    
   

2. next_permutation

由于next_permutation()函数在生成下一排列时候，会跳过重复情形，因此这道题和Permutations完全一样，利用next_permutation()函数，逐步生成下一个排列。由于next_permutation()在最后一个排列时返回false，因此可以先对数组排序，然后调用next_permutation()直到其返回false。

时间复杂度：O(n!)（结果数量）

空间复杂度：O(n!)

 1 class Solution
 2 {
 3 public:
 4     vector
   
     > permute(vector
    
      &num) 5 { 6 sort(num.begin(), num.end()); 7 8 vector
     
       > vvi({num}); 9 while(next_permutation(num.begin(), num.end())) 10 vvi.push_back(num); 11 12 return vvi; 13 } 14 };
     
    
   

?