回溯法应该知道的知识点

masbay 2020-12-19 原文

回溯法也可以叫做回溯搜索法，是一种搜索的方式，回溯和递归是相辅相成的，回溯是递归的副产品，只要有递归就会有回溯，所以可以简单的理解回溯函数和递归函数是同一个函数。

大名鼎鼎的回溯法虽然很不好理解，但其本质就是暴力查找，穷举所有可能，然后找出我们想要的答案，并不是什么高效的算法，虽然有些可以剪枝一下，没有更优化的方法了，至于为什么不高效还要用，那没别的更好的了能解决问题就不错了还想咋滴。

回溯法可以解决组合、排列、切割、子集、棋盘（N皇后，解数独）等问题，其中组合无序，排列有序。以上这几类问题都不简单。

回溯法解决的所有问题其实都可以抽象为树形结构，因为它解决的都是在结合中查找子集，集合的大小就构成了树的宽度，递归的深度构成树的深度（递归就要有终止条件，必然是一个棵高度有限的N叉树）。

和递归函数一样，三部曲：（1）确定回溯函数返回值和参数（一般不需要返回值，参数其实也不好确定，可以先写逻辑，再定参数）（2）终止条件（3）回溯搜索的遍历过程逻辑。

回溯法的问题有一个套用的模板帮助解决问题：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

终止条件说的就是一旦满足了要求的条件（一般来说搜索到叶子结点），就是找到了满足条件的一条答案，把这个答案存放起来，并接受这层递归。for循环是树的横向遍历，而递归调用时树的深度遍历，这样就能把一棵树都遍历到了。