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     vector<vector<int> > permuteUnique(vector<int> &num) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         vector<vector<int> > result;
 5         result.clear();
 6         int len = num.size();
 7         int i, j;
 8         if(len == 0)
 9             return result;
10         sort(num.begin(), num.end());
11         result.push_back(num);
12         while(true){
13             vector<int> tmp = result[result.size()-1];
14             i = len-1;
15             while(i > 0 && tmp[i] <= tmp[i-1]){
16                 i--;
17             }
18             if(i == 0)
19                 break;
20             i--;
21             j = len-1;
22             while(tmp[j] <= tmp[i]){
23                 j--;
24             }
25             int t = tmp[i];
26             tmp[i] = tmp[j];
27             tmp[j] = t;
28             i++;
29             j = len-1;
30             while(i < j){
31                 t = tmp[i];
32                 tmp[i] = tmp[j];
33                 tmp[j] = t;
34                 i++;
35                 j--;
36             }
37             result.push_back(tmp);
38         }
39         return result;
40     }