题目：
Given a collection of distinct numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
题解：
之前解过Next Permutation，故这个题可以重复调用nextPermutation函数产生全排列
Solution 1 ()
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
for(int i=n-; i>=; --i) {
if(nums[i]>=nums[i+]) continue;
int j = n-;
for(; j>i; --j) {
if(nums[j]>nums[i]) break;
}
swap(nums[i], nums[j]);
reverse(nums.begin()+i+, nums.end());
return;
}
reverse(nums.begin(), nums.end());
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> vv;
vector<int> v = nums;
vv.push_back(v);
nextPermutation(v);
while(v != nums) {
vv.push_back(v);
nextPermutation(v);
}
return vv;
}
};其实这个问题很容易想到递归的解法
for the length of n, the permutations can be generated by
(1) Swap the 1st element with all the elements, including itself.
(2) Then the 1st element is fixed, Go to the next element.
(3) Until the last element is fixed. Output.
It's more clear in the figure above. The key point is to make the big problem into smaller problem, here is how to convert the length n permutation into length n-1 permutation problem. from here and here
Solution 2 ()
class Solution {
public:
vector<vector<int> > permute(vector<int> &nums) {
vector<vector<int> > result;
permuteRecursive(nums, , result);
return result;
}
// permute nums[begin..end]
// invariant: nums[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &nums, int begin, vector<vector<int> > &result) {
if (begin >= nums.size()) {
// one permutation instance
result.push_back(nums);
return;
}
for (int i = begin; i < nums.size(); i++) {
swap(nums[begin], nums[i]);
permuteRecursive(nums, begin + , result);
// reset
swap(nums[begin], nums[i]);
}
}
};利用深度优先遍历遍历所有情况，DFS方法,用到一个数组来标记某个数字是否访问过,然后在DFS递归函数从的循环应从头开始，而不是从level开始，这是和Combinations 组合项不同的地方。
from here
Solution 3 ()
class Solution {
public:
vector<vector<int> > permute(vector<int> &nums) {
vector<vector<int> > res;
vector<int> out;
vector<int> visited(nums.size(), );
permuteDFS(nums, , visited, out, res);
return res;
}
void permuteDFS(vector<int> &nums, int level, vector<int> &visited, vector<int> &out, vector<vector<int> > &res) {
if (level == nums.size()) res.push_back(out);
else {
for (int i = ; i < nums.size(); ++i) {
if (visited[i] == ) {
visited[i] = ;
out.push_back(nums[i]);
permuteDFS(nums, level + , visited, out, res);
out.pop_back();
visited[i] = ;
}
}
}
}
};思路： from here
当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
Solution 4 ()
class Solution {
public:
vector<vector<int> > permute(vector<int> &nums) {
if (nums.empty()) return vector<vector<int> >(, vector<int>());
vector<vector<int> > res;
int first = nums[];
nums.erase(nums.begin());
vector<vector<int> > words = permute(nums);
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;
}
};