题目描述
Given a collection of distinct integers, return all possible permutations.
Example1:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解题思路
- 使用递归来输出全排列。首先明确的是 perm(arr, k, len) 函数的功能:输出字符数组 arr 从位置 k 开始的所有排列，数组长度为 len 。基础条件是 k == len-1，此时已经到达最后一个元素，一次排列已经完成，直接输出。否则，从位置k开始的每个元素都与位置k的值交换(包括自己与自己交换)，然后进行下一次排列，排列完成后记得恢复原来的序列。
- 假定数组 arr 大小 len=3，则程序调用 perm(arr, 0, 3) 可以如下理解：
- 第一次交换 0，0，并执行 perm(arr, 1, 3)，执行完再次交换0，0，数组此时又恢复成初始值。
- 第二次交换 1，0（注意数组此时是初始值），并执行 perm(arr, 1, 3), 执行完再次交换 1，0，数组此时又恢复成初始值。
- 第三次交换 2，0，并执行 perm(arr, 1, 3)，执行完成后交换2，0，数组恢复成初始值。
- 程序运行输出结果为：abc acb bac bca cba cab。即先输出以 a 为排列第一个值的排列，而后是 b 和 c 为第一个值的排列。
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
if(nums.size() == 0){
return res;
}
dfs(nums, 0);
return res;
}
void dfs(vector<int>& nums, int level){
if(level == nums.size()){
res.push_back(nums);
}
for(int i = level; i < nums.size(); i++){
swap(nums[i], nums[level]);
dfs(nums, level + 1);
swap(nums[i], nums[level]);
}
}
};
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
fun_helper(nums, 0, res);
return res;
}
void fun_helper(vector<int>& nums, int begin, vector<vector<int>>& res){
if(begin >= nums.size()){
res.push_back(nums);
}
for(int i = begin; i < nums.size(); i++){
swap(nums[i], nums[begin]);
fun_helper(nums, begin + 1, res);
swap(nums[i], nums[begin]);
}
}
};
