回溯，不难！

大家好，我是吴师兄。

这几天给训练营的同学总结回溯算法的题，发现没有想象中那么难，甚至可以说有套路，半小时可以学会。

简单来说，回溯算法是依托于 DFS 实现的，也是需要朝着一个方向不断的延伸搜索下去，但是回溯算法会在搜索过程中，达到结束条件时，恢复原状态，回溯到上一层，再次搜索。

即，回溯算法与 DFS 的区别是有无状态重置。

一般来说，回溯算法的思考步骤如下：

1、画出递归树，找到状态变量(回溯函数的参数)

2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件

3、确定选择列表，即需要把什么数据存储到结果里面

4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过

5、做出选择，递归调用该函数，进入下一层继续搜索

6、撤销选择，回到上一层的状态

翻译成代码为如下的形式，也就是回溯算法解题的一个模板：

// 1、画出递归树，找到状态变量(回溯函数的参数)
private void backtrack("原始参数") {
  
    // 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
    if ("终止条件") {
        // 一些逻辑操作（可有可无，视情况而定）
       // 比如，在 N 皇后问题中，在这一步把数据加入到了结果里面
        return;
    }
  
   // 3、确定选择列表，即需要把什么数据存储到结果里面
   // for 循环就是一个选择的过程
    for ("遍历本层集合中元素") {
      
        // 一些逻辑操作（可有可无，视情况而定）
       // 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过

        // 5、做出选择，递归调用该函数，进入下一层继续搜索
        // 递归
        backtrack("新的参数");
      
        // 一些逻辑操作（可有可无，视情况而定）

        // 6、撤销选择，回到上一层的状态
    }
}

按照这个思路，可以解决子集、组合、排列、N 皇后、岛屿等十几道回溯算法题。

给大家看一下效果。

结合动画来理解，半小时掌握 9 道回溯算法题是很轻松的。

明天把所有代码贴出来，让大家体验一下半小时刷 9 道回溯算法题的快感：）

最后

这是我们每天学会一点知识的第 51 天，当前进度 51/100。

我已经将大部分算法题解文章同步到了个人网站，方便阅读。

“网站地址：https://www.cxyxiaowu.com/”