Description
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]
]
Solution 1(C++)
class Solution {
public:
vector<vector<int>> permute(
vector<int>& nums) {
vector<vector<int>> res;
getPermutations(nums,
0, res);
return res;
}
private:
void getPermutations(
vector<int>& nums,
int begin,
vector<vector<int>>& res){
if (begin >= nums.size()) {
res.push_back(nums);
return;
}
for (
int i = begin; i < nums.size(); i++) {
swap(nums[begin], nums[i]);
getPermutations(nums, begin +
1, res);
swap(nums[begin], nums[i]);
}
}
};
Solution 2(C++)
class Solution {
public:
vector<vector<int> > permute(
vector<int> &num) {
vector<vector<int> > permutations(
1,
vector<int>());
for (
vector<int>::size_type index =
0; index != num.size(); ++index)
{
vector<vector<int> > subPermutations(permutations);
permutations.clear();
for (
vector<vector<int> >::size_type i =
0; i != subPermutations.size(); ++i)
{
for (
int offset =
0; offset != subPermutations[i].size()+
1; ++offset)
{
vector<int> temp(subPermutations[i]);
temp.insert(temp.begin() + offset, num[index]);
permutations.push_back(temp);
}
}
}
return permutations;
}
};
Solution 3(C++)
class Solution {
public:
vector<vector<int>> permute(
vector<int>& nums) {
vector<vector<int> > res;
sort(nums.begin(),nums.end());
do{
res.push_back(nums);
}
while(next_permutation(nums.begin(),nums.end()));
return res;
}
};
算法分析
解法一： 观察题目给出的例子就会发现，1、2、3三个元素的全排列组合可以发现，6中全排列可以分为三种组合：1+(2,3)；2+(1,3)；3+(1,2)，其中，括号表示括号类的元素再全排列。那么上面的三种组合其实可以表示为数组[1,2,3]中数组中的元素分别成为首部元素。所以就有这里的交换：
swap(
nums[begin],
nums[i]);
然后就是递归，主要递归完还要交换回来：
swap(
nums[begin],
nums[i]);
解法二
解法二主要是按照全排列的数学思想来做，一个空集合，插入元素1，只有一个位置，一种可能；再插入元素2，有两个位置，1的前面和1的后面，1 * 2=2种可能；再插入元素3，对于单个排列有三个位置，但是有两种组合：[1,2]、[2,1]，故1 * 2 * 3=6种可能。所以这个解法中必须涉及插入的过程：
temp.
insert(temp.begin() + offset, num[index]);
解法三 调用了库函数：next _ permutation()，是库< algorithm >的函数，是一个求一个排序的下一个排列的函数，可以遍历全排列，与之完全相反的函数还有prev _ permutation()。关于这这个库可以额外整理一篇博客。这就不罗嗦了，掌握函数的调用即可。
程序分析
略。
