本文共 1505 字，大约阅读时间需要 5 分钟。

什么是回溯算法，先上百度百科定义：

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

总结，如下图，如果我们需要知道下图中从顶点1到顶点5总共有多少条路径，我们会先站在顶点1，会面临着两个选择[2,3]，如果选择顶点2，也会有两个选择[4,6]，假如我们选择4，只有一个选择直接到顶点5，发现顶点5是我们的终点，所以就会把[1,2,4,5]这条路径加入结果集，顶点5继续走发现没路了，就会回退到上一次选择，顶点4，发现顶点4也没有选择了，会继续回退到顶点2，到顶点2发现还有顶点6没走，就会走顶点6.循环以上步骤，直到没有任何选择了，循环结束。

总之，回溯就是每到一个点，管他三七二十一，选选择一条路径，怼下去，怼不通就回退到上一个继续怼，怼通了就加入结果集，直到所有路都怼完。

现在我们知道回溯算法是什么了之后，上框架，框架来自微信公众号：labuladong。

result = [] //结果集def backtrack(路径，选择列表): //定义函数	if 满足结束条件:		result.add(路径);  //加入结果集		return;	for 选择 in 选择列表:  //循环选择列表		做选择		backtract(路径，选择列表)	//递归		撤销选择

核心就是for循环里面的递归，在递归之前[做选择]，在递归之后[撤销选择]。

好了，框架上完了，我们直接上题目

全排列

class Solution {       /**    * 结果集    **/    List
   
    
     > res = new LinkedList<>();    public List
     
      
       > permute(int[] nums) {           backtrack(nums, new LinkedList
       
        ());        return res;    }    /**    * nums选择列表    * track 路径    **/    public void backtrack(int[] nums, LinkedList
        
          track){ //触发结束条件 if(track.size() == nums.length){ /** *加入结果集,用new LinkedList的原因是因为track指向的是一块内存， *如果不新创建一块内存空间放现在的结果，后续操作会更改内存里面的值， *最终导致所有结果一样 **/ res.add(new LinkedList(track)); return; } for(int num : nums){ //撤销不合法的选择 if(track.contains(num)) continue; //做选择 track.add(num); //递归，进入下一次决策 backtrack(nums, track); //撤销选择 track.removeLast(); } }}