力扣HOT100之回溯：46. 全排列

之前刷代码随想录的时间做过这道题，现在忘得干干净净了，无语(ˉ▽ˉ；)…，看了下之前关于这道题的思路，写的还是比较简单，紧张是基于卡尔的视频来写的，没看过视频的话看那篇博客有点费劲。这次就重新写一下。
这道题要求全排列，那么全部符合条件的排列各自存入一个一维数组，全部存储排列结果的一维数组存放到一个二维数组中，终极将二维数组返回。我们考虑界说一个全局变量path来收获不同的结果，直接额外界说一个回溯函数backtracking()，该函数吸收两个参数，一个是包罗全部元素的数组nums，另一个是已使用的元素数组used由于回溯函数肯定是递归函数，我们需要先明确递归的终止条件，当path.size() == nums.size()时阐明全部元素全都用上了，此时我们将path添加到result中并直接退出函数，否则我们进入递归主体，在主体中，我们遍历nums中的全部元素，并检查当前遍历到的元素nums是否已被使用，如果被使用，就直接跳过本轮循环，如果没使用过，就将nums添加到path中，而且将used设置为true。然后我们递归调用backtracking()获取下一层的排列，当递归调用结束后，需要及时回退，将nums从path中弹出，并及时将used标记回false。

1. class Solution {
2. public:
3.     vector<vector<int>> result;   //存放所有排列结果
4.     vector<int> path;   //用于记录各种不同的排列结果
5.     vector<vector<int>> permute(vector<int>& nums) {
6.         vector<bool> used(nums.size(), false);  //用于标记对应的元素是否已经被使用
7.         backtracking(nums, used);
8.         return result;
9.     }
10.     //回溯递归函数
11.     void backtracking(vector<int>& nums, vector<bool>& used){
12.         //递归终止条件
13.         if(path.size() == nums.size()){
14.             result.emplace_back(path);
15.             return ;
16.         }
17.         for(int i = 0; i < nums.size(); i++){
18.             if(used[i]) continue;   //遇到已经使用过的元素，直接跳过
19.             path.emplace_back(nums[i]);
20.             used[i] = true;
21.             backtracking(nums, used);
22.             used[i] = false;
23.             path.pop_back();
24.         }
25.     }
26. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告