LeetCode --- Permutations II
2015-03-03 14:57:50         来源：makuiyu的专栏

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

# 1. 递归排列

`````` 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

`````` 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 };``````