leetcode 46. Permutations (生成全排列，无重复元素)
Given a collection of distinct numbers, return all possible permutations.
思路：调用n-1次 leetcode 31 解题报告 中提到的算法即可。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 14时49分34秒
4File Name :46.cpp
5 ************************************************ */
6class Solution {
public:
1 void solve(vector<int> &nums)
2 {
3 int n = nums.size();
4 if (n==0) return;
5 int k = -1;
6 for ( int i = n-2 ; i >= 0 ; i--)
7 {
8 if (nums[i]<nums[i+1])
9 {
10 k = i ;
11 break;
12 }
13 }
14 if (k==-1)
15 {
16 reverse(nums.begin(),nums.end());
17 return;
18 }
19 int l = -1;
20 for ( int i = n-1 ; i > k ; i-- )
21 {
22 if (nums[k]<nums[i])
23 {
24 l = i ;
25 break;
26 }
27 }
28 swap(nums[l],nums[k]);
29 reverse(nums.begin()+k+1,nums.end());
30 }
31 vector<vector<int>> permute(vector<int>& nums) {
32 vector<vector<int> >res;
33 int n = nums.size();
34 int total = 1;
35 for ( int i = 2 ; i <= n ; i++) total*=i;
36 for ( int i = 1 ; i <= total; i++)
37 {
38 res.push_back(nums);
39 solve(nums);
40 }
return res;
}
};