Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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 {
7
8 public:
9
10 void solve(vector<int> &nums)
11 {
12 int n = nums.size();
13 if (n==0) return;
14 int k = -1;
15 for ( int i = n-2 ; i >= 0 ; i--)
16 {
17 if (nums[i]<nums[i+1])
18 {
19 k = i ;
20 break;
21 }
22 }
23 if (k==-1)
24 {
25 reverse(nums.begin(),nums.end());
26 return;
27 }
28 int l = -1;
29 for ( int i = n-1 ; i > k ; i-- )
30 {
31 if (nums[k]<nums[i])
32 {
33 l = i ;
34 break;
35 }
36 }
37 swap(nums[l],nums[k]);
38 reverse(nums.begin()+k+1,nums.end());
39 }
40 vector<vector<int>> permute(vector<int>& nums) {
41 vector<vector<int> >res;
42 int n = nums.size();
43 int total = 1;
44 for ( int i = 2 ; i <= n ; i++) total*=i;
45 for ( int i = 1 ; i <= total; i++)
46 {
47 res.push_back(nums);
48 solve(nums);
49 }
50
51 return res;
52 }
53
54};