【算法】回溯法四步走 (5)

注意：在选择完路径分支之后，一般都伴随着 递归深度 + 1，f(depth + 1)，即 在选择完路径分支之后，我们从根节点向下移了一个深度。

特别注意：depth和i是两个不一样的概念，有时候我们做题把它当成了一个概念，其实只是有时候depth和i恰好相等而已

做题的时候，建议 先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。

在画图的过程中思考清楚：

分支如何产生；

题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？

哪些搜索会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？

4. 回溯还原现场

4.回溯还原现场：若该节点所有选择已做完却仍然没有找到出口，那么我们需要回溯还原现场，将该节点重置为初始状态，回溯到一切都没有发生的时候，再退回去。（与递归函数之前的操作对称）

特别注意：这意味着我们使用递归函数那行的前后操作是对称的！
注意：回溯还原现场是必要的，如果不还原现场，那你的回溯有什么意义呢。。

类比：大雄出意外了，哆啦A梦坐时空机回到过去想要改变这一切，结果过去的一切都没有被重置到初始状态，回到过去大雄还是现在这种受伤的样子没有改变，那么回到过去有什么意义呢。

补充说明，这里的回溯还原现场对于方法栈内的方法参数或局部变量来说并不一定是必要的，因为我们回溯的时候可以把当前方法栈帧弹出，不会影响到回溯，弹出之后就是还原的现场。

也就是说，我们的方法内使用的是方法参数这种与栈相关的局部变量，我们是不需要回溯还原现场的，因为我们当回溯的时候自动将当前栈帧弹出了，这样就相当于还原现场了。

如 求解一棵树内从根节点出发到任意节点的目标节点和有几个满足目标节点和？

public void f(TreeNode root, int sum) { if (root == null) { return; } sum -= root.val; // 这是局部变量，存在虚拟机栈中，不需要还原现场，因为调用完会自动弹出栈帧。 if (sum == 0) { res++; } f(root.left, sum); f(root.right, sum); } 四步走举例 编写检测函数（非必须）

第一步，写出检测函数，来检测这个路径是否满足条件，是否能通过。
这个函数依据题目要求来编写，当然，如果要求不止一个，可能需要编写多个检测函数。

例如：凑算式

这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。

比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法？

要做出这个题，
第一步，要写出检测函数

public static int sum = 0; // 用来存放总共的解法数 public static double[] a = new double[10]; // 判断数组里前j个元素是否与t相同 /** * @param a 传入一个数组a * @param j 判断前j个元素 * @param t 是否与t相同 * @return */ public static boolean same(double[] a, int j, int t) { for (int i = 1; i < j; i++) { if (a[i] == t) { return true; } } return false; } /** * @param a 判断a数组是否满足表达式 * @return 如果满足就true，不满足就false */ public static boolean expression(double[] a) { if ((a[1] + a[2] / a[3] + (a[4] * 100 + a[5] * 10 + a[6]) / (a[7] * 100 + a[8] * 10 + a[9]) == 10)) return true; else return false; } 明确函数功能

由于此题要填数字，所以我们定义 choose(i) 的含义为：在算式中自动填入数字 i 。

寻找递归出口

第二步，要寻找递归出口，当1~9均已填入后，判断表达式是否成立，若成立，则输出。

// 如果选择的数字大于9，则代表1~9均已选完，判断是否满足表达式，输出选择的表达式 if (i > 9) { if (expression(a)) { for (int x = 1; x < 10; x++) { System.out.print(a[x] + " "); } System.out.println(); sum++; } return; } 明确所有路径

第三步，要知道这个递归是几个选择，即 几叉树。