核心思路回溯法填空格思想我们可以把全排列想象成有 n 个空格我们要把数组里的 n 个数一个一个填进去每个数只能用一次。回溯法就是模拟这个 “填空” 的过程从第一个空格开始尝试所有没被用过的数选一个数填进去标记为 “已使用”递归填下一个空格填完所有空格得到一个排列保存结果回溯把刚才填的数拿出来标记为 “未使用”尝试下一个数这就是回溯最核心的三步做选择 → 递归 → 撤销选择方法一标记数组版面试首选最好写、最好懂1. 思路详解用一个used布尔数组标记哪个数已经被用过了不能再选。终止条件当前排列的长度等于数组长度说明所有空格都填完了循环遍历所有数没被用过的就可以选做选择把数加入当前排列标记为已用递归填下一个位置撤销选择把数从当前排列移除标记为未用class Solution { public: //写一个回溯函数 void backtrack(vectorvectorint res,vectorint 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,first1,len); //撤销操作 swap(output[i],output[first]); } } vectorvectorint permute(vectorint nums) { vectorvectorint res; backtrack(res,nums,0,(int)nums.size()); return res; } };
