给定一个数字列表，返回其所有可能的排列，第十五题是没有重复的数字，是十六题是有重复的数字。
先来说没有重复数字的情况
n个数字有n!个全排列，每个数字都可以成为排列的第一个数字，然后剩下n-1个数字里可以找出第二个数字，之后剩下的n-2个数字里可以找到第三个数字，依次类推，最后只有一个数字可以放在第n个位置，因此可以采用回溯法，也可以叫做深度优先搜索。
我们以数组[1,2,3]为例，首先进入第一个for循环，i和start都为0，执行swap，此时为1和自身交换，接着进入递归，i和start都为1，执行swap，此时为2和自身交换，接着进行递归（start为2），3和自身交换，此时start等于了数组的长度，因此返回，得到的一个排列为[1,2,3]。然后返回上一层的递归函数（start为2），执行swap，3和自身交换，再返回上一层（start为1），执行swap，2和自身交换。接着进入下一个for循环（此时i和start都为1，而循环条件为i<num.size())，这时start为1，i为2，执行swap，2和3交换，num变为[1,3,2]，然后进入递归，start和i都为2，2和自身交换，接着递归，start等于数组长度，于是得到第二个排列[1,3,2]。然后返回（start为2），再返回（start为1），然后执行下一句swap，结果为2和3换回来，即数组变为[1,2,3]，接着返回（start为0），然后进行start为0的那个函数的for循环，将数组变为了[2,1,3]，然后以此类推，可以得到全部的全排列。
说的比较啰嗦，代码如下：
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int> nums) {
// write your code here
vector<vector<int>> result;
permutation(nums,result,0,nums.size());
return result;
}
void permutation(vector<int> num,vector<vector<int> > &res,int start,int end) {
if (start == end) {
res.push_back(num);
return;
}
for (int i = start;i < end;i++) {
swap(num[i],num[start]);
permutation(num,res,start+1,end);
swap(num[i],num[start]);
}
}
};
接下来是有重复数字的情况，大体的思路和没有重复数字的是一样的，但是如果swap两个一样的数字，就会产生重复，因此，加入一个条件判断，为了保证重复的数字都挨着，首先将数组进行排列。代码如下：
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
vector<vector<int> > permuteUnique(vector<int> &nums) {
// write your code here
sort(nums.begin(),nums.end());
vector<vector<int> > result;
permutation(result,nums,0);
return result;
}
void permutation(vector<vector<int> > &res,vector<int> num,int start) {
if (start == num.size()) {
res.push_back(num);
return;
}
for (int i = start;i < num.size();i++) {
if (start != i && num[start] == num[i]) continue;
swap(num[start],num[i]);
permutation(res,num,start + 1);
}
}
};
