- Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
1.常规思路:hash表用来标记hash[i] 是否已在序列中,cur是当前已排好的部分序列,n是排列好的个数。递归,回溯。空间开销很大
vector<vector<int>>res;
void traceback(vector<int>& nums,vector<bool>hash,vector<int>cur,int n){
if(n==nums.size()){
res.push_back(cur);
return;
}
for(int i=0;i<nums.size();i++){
if(!hash[i]){
hash[i]=true;
cur.push_back(nums[i]);
traceback(nums,hash,cur,n+1);
cur.pop_back();
hash[i]=false;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
map<int,int>m;
vector<bool>hash(nums.size());
vector<int>cur;
traceback(nums,hash,cur,0);
return res;
}
2.官方题解思路
使用变量first标记已经排好的序列,直接在原数组上修改。0~first-1是已经排好的,依次选择 [ first, n-1 ]的每一个元素,与first位置上的元素交换,递归搜索,标记位first+1。结束搜索的条件为first=n,表示前n个元素被排列完。回溯时交换回 i 和 first 位置上的元素。
vector<vector<int>>res;
void traceback(vector<int>&nums,int first){
if(first==nums.size()){
res.push_back(nums);
return;
}
for(int i=first;i<nums.size();i++){
swap(nums[i],nums[first]);
traceback(nums,first+1);
swap(nums[i],nums[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
traceback(nums,0);
return res;
}