回溯算法

什么是回溯呢？

使用 DFS 查找二叉树所有的路径：

回溯本质上是一种 暴力穷举算法，把所有的可能都列举出来，所以没有剪枝情况下的回溯是比较低效的。正因为这样，一般回溯会进行剪枝操作。所谓剪枝，指的就是当搜索到某个分支不可能得到可行解（或更优解）时，就 提前结束 该分支，避免进行无意义的搜索。

具体示例

🙋[1, 2, 3] 这 3 个数有多少种组合呢？

就是将所有的结果都穷举出来：

• 第一位选 1，第二位从 [2, 3] 里面去选，第二位选择的是什么又影响第三位
• 第一位选 2，第二位从 [1, 3] 里面去选，第二位选择的是什么又影响第三位
• 第一位选 3，第二位从 [1, 2] 里面去选，第二位选择的是什么又影响第三位

这里可以将选择的过程抽象为一颗树：

算法模板

整个回溯算法，可以看作是一个树的遍历过程，因此整个回溯算法有如下的算法模板：

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

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

回溯能解决的问题

1. 组合问题：N个数按照一定的规则找出 k 个数的集合
2. 切割问题：一个字符串按照一定的规则进行切割，看有多少种切割方式
3. 子集问题：一个 N 个数的集合里面有多少符合条件的子集
4. 排列问题：N 个数按照一定规则来进行排列，看有多少种排列的方式
5. 棋盘问题

-EOF-