回朔法的重要思想在于: 通过枚举法,对所有可能性进行遍历。 但是枚举的顺序是 一条路走到黑,发现黑之后,退一步,再向前尝试没走过的路。直到所有路都试过。因此回朔法可以简单的理解为: 走不通就退一步的方枚举法就叫回朔法。而这里回退点也叫做回朔点。
1、如果解决一个问题有多个步骤,每一个步骤有多种方法,题目又要我们找出所有的方法,可以使用回溯算法;
回溯算法是在一棵树上的 深度优先遍历(因为要找所有的解,所以需要遍历);
2、回溯算法首先需要画出递归树,不同的树决定了不同的代码实现。下面给出了两种画树的思路。!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
回溯法,一般可以解决如下几种问题:
2、模板
解释:回溯算法中函数返回值一般为void。
集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。
- void backtracking(参数) { //参数一般边写边添加,一开始不能全部确定
- if (终止条件) { //一般为空
- 存放结果;
- return;
- }
-
- for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { //for循环横向遍历,遍历n叉树的所有孩子。
- 处理节点;
- backtracking(路径,选择列表); // 递归 :纵向遍历
- 回溯,撤销处理结果
- }
- }
如图:回溯算法首先需要画出递归树,不同的树决定了不同的代码实现。下面给出了两种画树的思路。
1、减宽度,就是舍弃掉当前层的有些元素(组合问题),如果,后面的元素个数,已经不够 题目要求的个数,直接return
2、减深度,若题目类型是带 和 等一些条件的约束(组合求和),如果遍历到该元素, 和 已经不满足条件了,就直接return