LeetCode --- 46. Permutations

題目鏈接：Permutations

Given a collection of numbers, return all possible permutations.

For example,

[1,2,3] have the following permutations: 
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. 

這道題的要求是給定一組數字，生成所有的排列組合。

1. 遞歸排列

這是一個排列的問題，首先聯想到的就是遞歸方式。每次逐個固定每個元素到第一位置，然後遞歸排列剩下的元素。當固定到前面的元素數量等於數組長度的時候，遞歸終止。

時間復雜度：O(n!)（結果數量）

空間復雜度：O(n!)

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

2. next_permutation

其實還可以利用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 };