专题：回溯算法

参考：代码随想录回溯专题（https://www.bilibili.com/video/B...36d0f96fb45a10e6e1e）


首先，回溯的逻辑是暴力搜索，即遍历所有的可能情况。刚开始学习算法的同学可能会混淆回溯和递归，但只要了解了回溯暴力搜索的本质，就很容易分清楚两者了。


既然回溯是暴力搜索，那么本质上和写for循环也没有区别。只不过很多回溯的题目嵌套的for循环层数较多，因此需要用递归法来实现。


搜索的过程可以可视化成一棵树，其中每层的可能的节点取值是基于当前状态下的可能选择。


下面举一个很简单的例子加以阐述：寻找{1,2,3}所有和为3的组合（集合中所有元素为正整数且不重复）。


                                  { }
                              /     |     \
                             1      2      3
                            / \       \
                           2  3      3
                           /
                          3


首先，树的第一层可供选择的value是1，2，3。第二层之后，我们只选取当index大于当前节点的value作为备选项，防止重复选。当路径上value之和为3时，收集节点所表示的组合。


回溯之所以叫回溯算法，是因为遍历的时候用的是深度优先搜索，因此达到叶子节点之后，需要退回到上一层的节点继续搜索。因为我们会用一个变量存储当前组合，因此回退的时候需要把之前加入的value弹出。当然如果你每次用一个新变量存储当前组合并把新变量传入递归函数，省略弹出这一步也是可以的，就是空间消耗会增加，所以一般都用同一个变量储存组合，然后把指针传人递归函数。


剪枝操作可以降低时间复杂度。在这个例子中，因为元素都是正整数，所以当前组合大于等于3之后就不用再往深处搜索了。同时，如果我们把集合内元素排序，也可以在同一层内进行剪枝操作，如果当前组合大于等于3，则不用再搜下一个sibling了。