核心思路：回溯法（填空格思想）
我们可以把全排列想象成：有 n 个空格，我们要把数组里的 n 个数，一个一个填进去，每个数只能用一次。
回溯法就是模拟这个 “填空” 的过程：
- 从第一个空格开始，尝试所有没被用过的数
- 选一个数填进去，标记为 “已使用”
- 递归填下一个空格
- 填完所有空格，得到一个排列，保存结果
- 回溯：把刚才填的数拿出来，标记为 “未使用”，尝试下一个数
这就是回溯最核心的三步：做选择 → 递归 → 撤销选择
方法一：标记数组版（面试首选，最好写、最好懂）
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; } };