递归练习三（决策树）
一、解题心得
当我们需要暴力搜索全部的解时可以考虑用递归，解决方法就是画出决策树，由于二叉树的性质可以知道二叉树的分支代表两种情况，此时如果画出所有情况就是画出了决策树，又由于树的遍历用的是递归，所以就可以遍历决策树来添加出所有的解。
二、例题
1、全排列
分析
全排列可以有两种方法
（1）按位解决
顾名思义就是分析每一位上是什么数字。要求就是前面出现的数字在这一位上不能再出现。按位解决可以画出决策树：
（2）按层解决
规定第 n 层只能有 n 个数字
n 数的全排列就是在 n - 1 数全排列的基础上，把第 n 个数插入到每一个 n - 1 数全排列数组的 n 个位置
举例：[1, 2, 3]
1
12 21
312 231 123 321 231 213
代码
（1）按位解决
（2）按层解决
2、子集
分析
有三种解决办法，两种决策树，一种按层解决
（1）决策树1
子集与全排列的区别就是全排列每一位必须选，子集每一位可以选可以不选。
由此第一种决策树结果出现在叶子节点。
决策树：
（2）决策树2
递归到数 i 的时候，i 以及 i 之后的值也是可以加入到之前存好的路径的，所以每一次的加入都是一个新的结果。
决策树：
（3）按层解决
规定第 n 层只能有 n 个数字
为了保证每层添加数字时不重不漏，只会添加比前一个数大的数，即子集都是升序。
举例：[1, 2, 3]
1 2 3
12 13 23
123 空
代码
（1）决策树1
（2）决策树2
（3）按层解决
三、总结
用决策树解决问题时一般结果在根到叶子的路径上，叶子节点或就是递归的每一次。
所以有很多时候都是要用到全局变量 tmp 来记录每一层递归的路径，当然只要在本层修改路径，回溯时就一定要把路径还原，这样才能让下一次递归有正确的路径。
原文地址：https://blog.csdn.net/qhy850716/article/details/145211932
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！