LeetCode 【46. Permutations】

时间:2024-12-23 18:06:26

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]
] 思路:
首先,固定第一个数字,递归求后序数组的全排列,比如example中,递归过程为:固定1,求[2,3]的全排列,然后固定2,求[3]的全排列,固定[3]求,空数组的全排列,由于此时数组为空,所以将结果保存,返回。
然后交换位子,继续进行递归,说的有点不是很明白,看一张图就比较清晰了。如图是一颗枚举树。现在的问题是怎么出现1,2,3开头的节点呢?就是使用交换,比如1和2交换,得到[2,1,3]固定2,求[1,3]的全排列。
那交换以后怎么得到3开头的呢?由于是递归,所以可以交换回1,2然后再交换1,3得到3开头的。

LeetCode 【46. Permutations】

代码

class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
permuteRec( 0, nums, result);
return result;
} private:
void permuteRec( int start, vector<int> &nums, vector<vector<int>> &result ){
if( start >= nums.size()){
result.push_back(nums);
return;
}
for( int i = start; i < nums.size(); i++ ){
       swap( nums[start], nums[i] );
permuteRec( start+1, nums, result);
swap( nums[start], nums[i] );
}
}
};