力扣HOT100（35）回溯-全排列

核心思路：回溯法（填空格思想）

我们可以把全排列想象成：有 n 个空格，我们要把数组里的 n 个数，一个一个填进去，每个数只能用一次。

回溯法就是模拟这个 “填空” 的过程：

1. 从第一个空格开始，尝试所有没被用过的数
2. 选一个数填进去，标记为 “已使用”
3. 递归填下一个空格
4. 填完所有空格，得到一个排列，保存结果
5. 回溯：把刚才填的数拿出来，标记为 “未使用”，尝试下一个数

这就是回溯最核心的三步：做选择 → 递归 → 撤销选择

方法一：标记数组版（面试首选，最好写、最好懂）

1. 思路详解

用一个used布尔数组，标记哪个数已经被用过了，不能再选。

• 终止条件：当前排列的长度等于数组长度，说明所有空格都填完了
• 循环：遍历所有数，没被用过的就可以选
• 做选择：把数加入当前排列，标记为已用
• 递归：填下一个位置
• 撤销选择：把数从当前排列移除，标记为未用

class Solution { public: //写一个回溯函数 void backtrack(vector<vector<int>>& res,vector<int>& output,int first,int len){ /*output：当前的数组 first：现在要填第几个位置 len：数组长度（固定不变） i：用来遍历，把后面的数字一个个换到 first 位置*/ //填完了 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]); } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; backtrack(res,nums,0,(int)nums.size()); return res; } };