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开头的。
代码
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] ); } } };