LeetCode/全排列
给定一个不含重复数字的数组nums，返回其所有可能的全排列，你可以按任意顺序返回答案
回溯法
思路：每次选一个，转移到下一空间，考虑用回溯思想，遍历可选数，递归每一位，当最后一位选取结束时记录结果
粗糙写法
class Solution {
public:
vector> res;
int len;
unordered_set sets;
vector> permute(vector& nums) {
vector num;
len=nums.size();
backtrack(nums,num,0);
return res;
}
void backtrack(vector& nums,vector& num,int index){
if(index==len){
res.push_back(num);
return;
}
for(int i=0;i0) continue;
num.push_back(nums[i]);
sets.insert(nums[i]);
backtrack(nums,num,index+1);
num.pop_back();
sets.erase(nums[i]);
}
}
};
优化写法
class Solution {
public:
vector> res;
vector> permute(vector& nums) {
vector num;
backtrack(nums,num);
return res;
}
void backtrack(vector& nums,vector& num)
{
if(num.size()==nums.size()){
res.push_back(num);
return;
}
for(int i=0;i 官方无敌写法
class Solution {
public:
vector> permute(vector& nums) {
vector > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
void backtrack(vector>& res, vector& output, int first, int len){
// 所有数都填完了
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 动态维护数组
swap(output[i], output[first]);
// 继续递归填下一个数
backtrack(res, output, first + 1, len);
// 撤销操作
swap(output[i], output[first]);
}
}
};