Medium!
题目描述：
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解题思路：
这道题是求全排列问题，给的输入数组没有重复项，这跟之前的那道Combinations 组合项 和类似，解法基本相同，但是不同点在于那道不同的数字顺序只算一种，是一道典型的组合题，而此题是求全排列问题，还是用递归DFS来求解。这里我们需要用到一个visited数组来标记某个数字是否访问过，然后DFS递归函数循环应从头开始，而不是从level开始，这是和Combinations 组合项 不同的地方，其余思路大体相同。
C++解法一：
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > res;
vector<int> out;
vector<int> visited(num.size(), );
permuteDFS(num, , visited, out, res);
return res;
}
void permuteDFS(vector<int> &num, int level, vector<int> &visited, vector<int> &out, vector<vector<int> > &res) {
if (level == num.size()) res.push_back(out);
else {
for (int i = ; i < num.size(); ++i) {
if (visited[i] == ) {
visited[i] = ;
out.push_back(num[i]);
permuteDFS(num, level + , visited, out, res);
out.pop_back();
visited[i] = ;
}
}
}
}
};还有一种递归的写法，更简单一些，这里是每次交换num里面的两个数字，经过递归可以生成所有的排列情况，代码如下。
C++解法二：
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > res;
permuteDFS(num, , res);
return res;
}
void permuteDFS(vector<int> &num, int start, vector<vector<int> > &res) {
if (start >= num.size()) res.push_back(num);
for (int i = start; i < num.size(); ++i) {
swap(num[start], num[i]);
permuteDFS(num, start + , res);
swap(num[start], num[i]);
}
}
};最后再来看一种方法，这种方法是CareerCup书上的方法，也挺不错的，这道题是思想是这样的：
当n=1时，数组中只有一个数a，其全排列只有一种，即为a
当n=2时，数组中此时有aa，其全排列有两种，aa和aa，那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在a的前后两个位置分别加入了a
当n=3时，数组中有aaa，此时全排列有六种，分别为aaa, aaa, aaa, aaa, aaa, 和 aaa。那么根据上面的结论，实际上是在aa和aa的基础上在不同的位置上加入a而得到的。
_ a_ a_ : aaa, aaa, aaa
_ a_ a_ : aaa, aaa, aaa
C++解法三：
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
if (num.empty()) return vector<vector<int> >(, vector<int>());
vector<vector<int> > res;
int first = num[];
num.erase(num.begin());
vector<vector<int> > words = permute(num);
for (auto &a : words) {
for (int i = ; i <= a.size(); ++i) {
a.insert(a.begin() + i, first);
res.push_back(a);
a.erase(a.begin() + i);
}
}
return res;
}
};