经典算法之-回溯法

1、什么是回溯法

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。 但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

2、回溯法的效率

回溯法的效率，说到效率，其实回溯法并不是什么高效的算法，也不能称之为一种算法，更像是一种模板，一种固定形式的写法；

因为回溯的本质就是穷举，穷举所有的可能，然后在穷举的过程中，提取我们需要的结果。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。

3、回溯法能解决的问题

LeetCode 17. 电话号码的字母组合
LeetCode 77. 组合
LeetCode 216. 组合总和 III

组合是不强调元素顺序的，排列是强调元素顺序。

4、掌握回溯法

人的脑回路不是无穷的，一般人只需要能递归两到三层就够了，再多会导致思维混乱，所以想要“形象”的掌握回溯，那就把它想象成“一棵树”。

回溯算法模板框架如下:

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

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