46. Permutations

题目描述：

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路：

用回溯法。使用额外空间记录每个数值是否已经使用。

代码：

 1 class Solution {
 2 public:
 3     vector<vector<int>> permute(vector<int>& nums) {
 4         int size = nums.size();
 5         vector<int> flag(size, 0);
 6         vector<vector<int> > ret;
 7         vector<int> tmp;
 8         tmp.reserve(size);   
 9         permute(size, flag, tmp, ret);
10         for (int i = 0; i < ret.size(); i++) {
11             for (int j = 0; j < size; j++) {
12                 ret[i][j] = nums[ret[i][j]];
13             }
14         }
15         return ret;
16     }
17     void permute(int size, vector<int>& flag, vector<int>& tmp, vector<vector<int> >& ret) {
18         if (accumulate(flag.begin(), flag.end(), 0) == size) {
19             ret.push_back(tmp);
20         }
21         for (int i = 0; i < size; i++) {
22             if (flag[i])
23                 continue;
24             flag[i] = 1;
25             tmp.push_back(i);
26             permute(size, flag, tmp, ret);
27             tmp.pop_back();
28             flag[i] = 0;
29         }
30     }
31 };

View Code

改进版本：

 1 class Solution {
 2 public:
 3     vector<vector<int>> permute(vector<int>& nums) {
 4         int size = nums.size();
 5         vector<int> flag(size, 0);
 6         vector<vector<int> > ret;
 7         vector<int> tmp;
 8         tmp.reserve(size);   
 9         permute(size, nums, flag, tmp, ret);
10         /*for (int i = 0; i < ret.size(); i++) {
11             for (int j = 0; j < size; j++) {
12                 ret[i][j] = nums[ret[i][j]];
13             }
14         }*/
15         return ret;
16     }
17     void permute(int size, const vector<int>& nums, vector<int>& flag, vector<int>& tmp, vector<vector<int> >& ret) {
18         if (accumulate(flag.begin(), flag.end(), 0) == size) {
19             ret.push_back(tmp);
20             return;
21         }
22         for (int i = 0; i < size; i++) {
23             if (flag[i])
24                 continue;
25             flag[i] = 1;
26             tmp.push_back(nums[i]);
27             permute(size, nums, flag, tmp, ret);
28             tmp.pop_back();
29             flag[i] = 0;
30         }
31     }
32 };

View Code