给定一个没有重复数字的序列，返回它所有可能的完整排列。示例：输入：[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]思路至此我们学习了组合问题、分段回文串和子集问题。接下来，让我们看一下排列问题。相信即使这个排列题让你用for循环暴力搜索出结果，这个暴力也不是很好写的。所以就像我们在谈论回溯算法一样，你应该知道这个！为什么回溯法是暴力搜索，效率这么低，还用？因为有些问题是可以暴力查出来的！我想以[1,2,3]为例，抽象成树状结构如下：全置换回溯三部曲的递归函数的参数先按顺序排列，即[1,2]和[2,1]是两个集合，与之前分析的子集和组合不同。可以看出在[1,2]中已经使用了元素1，但是在[2,1]中又使用了1，所以不需要使用startIndex来处理排列问题。但是排列问题需要一个used数组来标记选中的元素，如图橙色部分所示：完整的排列代码如下：vector>result;vectorpath;voidbacktracking(vector&nums,vector&used)递归终止条件的完整排列表明叶节点是收获结果的地方。那么什么时候才算到达了叶节点呢？当收集元素的数组路径大小达到和nums数组一样大的时候，就说明找到了全排列，也说明到了叶子节点。代码如下：//此时说明已经找到一组if(path.size()==nums.size()){result.push_back(path);return;}。单层搜索的逻辑就到这里了，组合问题和裁剪问题与子集问题最大的区别就是for循环中没有使用startIndex。因为排列问题，每次都得从头找。比如元素1已经在[1,2]中使用过，但是在[2,1]中需要再次使用1。used数组其实就是记录了此时使用了路径中的哪些元素，一个数组中的一个元素只能被使用一次。代码如下：for(inti=0;i>结果；vectorpath;voidbacktracking(vector&nums,vector&used){//此时一组if(path.size()==nums.size()){result.push_back(path);return;}for(inti=0;i>permute(vector&nums){result.clear();path.clear();vectorused(nums.size(),false);回溯(nums,used);returnresult;}};综上所述，此时可以感受到排列问题的区别：每一层都是从0开始查找，而不是从startIndex开始查找。used数组需要记录路径中放置了哪些元素。排列问题是回溯算法解决的经典问题，大家可以好好体验一下。本文转载自微信公众号《代码随想录》，可通过以下二维码关注。转载本文请联系CodeCaprice公众号。
