力扣HOT100之回溯：46. 全排列
https://i-blog.csdnimg.cn/direct/056bd13a3f68401b9d8beb786d631322.png之前刷代码随想录的时间做过这道题，现在忘得干干净净了，无语(ˉ▽ˉ；)…，看了下之前关于这道题的思路，写的还是比较简单，紧张是基于卡尔的视频来写的，没看过视频的话看那篇博客有点费劲。这次就重新写一下。
这道题要求全排列，那么全部符合条件的排列各自存入一个一维数组，全部存储排列结果的一维数组存放到一个二维数组中，终极将二维数组返回。我们考虑界说一个全局变量path来收获不同的结果，直接额外界说一个回溯函数backtracking()，该函数吸收两个参数，一个是包罗全部元素的数组nums，另一个是已使用的元素数组used由于回溯函数肯定是递归函数，我们需要先明确递归的终止条件，当path.size() == nums.size()时阐明全部元素全都用上了，此时我们将path添加到result中并直接退出函数，否则我们进入递归主体，在主体中，我们遍历nums中的全部元素，并检查当前遍历到的元素nums是否已被使用，如果被使用，就直接跳过本轮循环，如果没使用过，就将nums添加到path中，而且将used设置为true。然后我们递归调用backtracking()获取下一层的排列，当递归调用结束后，需要及时回退，将nums从path中弹出，并及时将used标记回false。
class Solution {
public:
vector<vector<int>> result; //存放所有排列结果
vector<int> path; //用于记录各种不同的排列结果
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);//用于标记对应的元素是否已经被使用
backtracking(nums, used);
return result;
}
//回溯递归函数
void backtracking(vector<int>& nums, vector<bool>& used){
//递归终止条件
if(path.size() == nums.size()){
result.emplace_back(path);
return ;
}
for(int i = 0; i < nums.size(); i++){
if(used) continue; //遇到已经使用过的元素，直接跳过
path.emplace_back(nums);
used = true;
backtracking(nums, used);
used = false;
path.pop_back();
}
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]