#### 方法一：

``````class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > ans;
sort(num.begin(), num.end());

ans.push_back(num);

while(next_permutation(num.begin(), num.end()))
ans.push_back(num);
return ans;
}
};``````

Runtime: 8 ms, faster than 98.88% of C++ online submissions for Permutations.
Memory Usage: 9.1 MB, less than 100.00% of C++ online submissions for Permutations.

#### 方法二：

``````class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
permuteRecursive(num, 0, result);

return result;
}

private:
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)
{
if(begin >= num.size())
{
result.push_back(num);
return;
}

for(int i = begin;i < num.size();i++)
{
swap(num[i],num[begin]);
permuteRecursive(num, begin + 1, result);
swap(num[i],num[begin]);
}

}
};``````

Runtime: 12 ms, faster than 71.01% of C++ online submissions for Permutations.
Memory Usage: 9.2 MB, less than 94.03% of C++ online submissions for Permutations.

``````#include <iostream>
#include <vector>
using namespace std;

// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)
{
if (begin >= num.size()) {
// one permutation instance
result.push_back(num);
return;
}

for (int i = begin; i < num.size(); i++) {
swap(num[begin], num[i]);
permuteRecursive(num, begin + 1, result);
// reset
swap(num[begin], num[i]);
}
}

vector<vector<int> > permute(vector<int> &num)
{
vector<vector<int> > result;

permuteRecursive(num, 0, result);
return result;
}

int main()
{
vector <int> nums{1,2,3};
vector<vector<int>> ans = permute(nums);

for(auto iter = ans.begin();iter != ans.end();iter++)
{
for(auto it = (*iter).begin();it != (*iter).end();it++)
{
cout << *it <<" ";
}
cout << "\n";
}
return 0;
}``````

gdb调试结果：

``````Breakpoint 1, main () at leetcode.cc:32
32  {
(gdb) n
33      vector <int> nums{1,2,3};
(gdb)
34      vector<vector<int>> ans = permute(nums);
(gdb) s
permute (num=std::vector of length 3, capacity 3 = {...}) at leetcode.cc:24
24  {
(gdb) n
25      vector<vector<int> > result;
(gdb) n
27      permuteRecursive(num, 0, result);
(gdb) s
permuteRecursive (num=std::vector of length 3, capacity 3 = {...}, begin=0, result=std::vector of length 0, capacity 0)
at leetcode.cc:9
9       if (begin >= num.size()) {
(gdb) n
15      for (int i = begin; i < num.size(); i++) {
(gdb) p begin
\$1 = 0
(gdb) n
16          swap(num[begin], num[i]);
(gdb) p num
\$2 = std::vector of length 3, capacity 3 = {1, 2, 3}
(gdb) n
17          permuteRecursive(num, begin + 1, result);
(gdb) p num
\$3 = std::vector of length 3, capacity 3 = {1, 2, 3}
(gdb) p result
\$4 = std::vector of length 0, capacity 0
(gdb) n
19          swap(num[begin], num[i]);
(gdb) n
15      for (int i = begin; i < num.size(); i++) {
(gdb) p result
\$5 = std::vector of length 2, capacity 2 = {std::vector of length 3, capacity 3 = {1, 2, 3},
std::vector of length 3, capacity 3 = {1, 3, 2}}
(gdb) n
16          swap(num[begin], num[i]);
(gdb) p i
\$6 = 1
(gdb) p num
\$7 = std::vector of length 3, capacity 3 = {1, 2, 3}
(gdb) n
17          permuteRecursive(num, begin + 1, result);
(gdb) p num
\$8 = std::vector of length 3, capacity 3 = {2, 1, 3}
(gdb) n
19          swap(num[begin], num[i]);
(gdb) p result
\$9 = std::vector of length 4, capacity 4 = {std::vector of length 3, capacity 3 = {1, 2, 3},
std::vector of length 3, capacity 3 = {1, 3, 2}, std::vector of length 3, capacity 3 = {2, 1, 3},
std::vector of length 3, capacity 3 = {2, 3, 1}}
(gdb) n
15      for (int i = begin; i < num.size(); i++) {
(gdb) n
16          swap(num[begin], num[i]);
(gdb) p i
\$10 = 2
(gdb) p num
\$11 = std::vector of length 3, capacity 3 = {1, 2, 3}
(gdb) n
17          permuteRecursive(num, begin + 1, result);
(gdb) p num
\$12 = std::vector of length 3, capacity 3 = {3, 2, 1}
(gdb) n
19          swap(num[begin], num[i]);
(gdb) p result
\$13 = std::vector of length 6, capacity 8 = {std::vector of length 3, capacity 3 = {1, 2, 3},
std::vector of length 3, capacity 3 = {1, 3, 2}, std::vector of length 3, capacity 3 = {2, 1, 3},
std::vector of length 3, capacity 3 = {2, 3, 1}, std::vector of length 3, capacity 3 = {3, 2, 1},
std::vector of length 3, capacity 3 = {3, 1, 2}}
(gdb)``````

``````class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
permuteRecursive(num, 0, result);

return result;
}

private:
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)
{
if(begin >= num.size() - 1)
{
result.push_back(num);
return;
}

for(int i = begin;i < num.size();i++)
{
swap(num[i],num[begin]);
permuteRecursive(num, begin + 1, result);
swap(num[i],num[begin]);
}

}
};``````