“递归只在天上。 人之间也有反复”，从这句话中可以看出递归的精妙。 确实很厉害。 递归是逐渐减小问题的规模。
然后，推回去，本质上从最小规模到目标值，思想是数学归纳法。 举个例子，求阶乘n！=(n-1 )！ *N、
另一方面，反复是数学中的极限思想，利用上次的结果，逐渐接近目标值。 在迭代过程中规模不变。 例如，For循环达到终止条件。
递归的思想并不复杂，但代码的理解很麻烦。 理解brdzfj数组的递归也不难。 例如，在下一个回溯算法递归、for循环中
带着递归，看了代码晕了吗？ 那么，就谈谈这个框架吧！
作者原创文章，谢绝一切形式转载。 违者一定追究！
准备：
Idea2019.03/JDK11.0.4
难度：初学者---战士---退伍军人---大师
目标：
回溯算法分析与应用
1回溯算法
首先给出了回溯算法的框架：
后退(路径，选择列表)
//结束条件
将中间结果添加到结果集中
for选择in选择列表：
//进行选择，然后从选择列表中删除该选择
路径. add (选择) )
后退(路径，选择列表) )。
//取消选择
路径. remove (选择)
}
为了理解上述算法，如前一篇文章所述，多重树扫描算法的框架：
私有状态类节点{
公共int value；
公共节点[ ] children；
}
publicstaticvoidDFS(noderoot ) {
if(root==null ) {
返回；
}
//按前序遍历位置，对node做某事
for(nodechild3360children
() )。
DFS(child )；
}
//稍后遍历位置，对node做某事
}
如果去掉添加/撤消路径的逻辑，不是和多重树遍历算法的框架一样吗？ 其实是多重树DFS的变种算法！
此外，递归代码很难理解，在运行时是堆栈实现，但不要落入递归堆栈。 不这样做的话就出不来。 如果你用断点试试，
你得想办法逐行跟进。 那很抱歉，可能连三餐的功夫都做不到。 此外，我怀疑自己的智商。 所以，理解递归
核心是抓住函数体来看。 抽象地理解，只知道n和N-1的转移逻辑就可以了。 不明白的地方应用之后再说，也许总有一天会有灵感
灵光一闪！
那我先上菜了！ 首先建立经典的回溯算法，代号a，数组全数组。 我想别人也在谈论回溯算法这个例子
我成了俗人：
类性能{
//排列组合算法
privatestaticlistoutput=new linked list (；
staticlistpermute(listnums，//要排列的数组
int start //开始位置
() )。
if(start==nums.size () ) ) ) ) ) )。
output.add(newArraylist ) nums )；
}
for(intI=start； i nums.size (； I ) {
//选择以交换元素的位置
collections.swap(NUMS，start，I )；
//递归地缩小规模
permute(nums，start 1)；
//取消选择，追溯到原来的状态，
collections.swap(NUMS，start，I )；
}
返回输出；
}
//测试
publicstaticvoidmain (string [ ] args ) {
listnums=arrays.as list (1，2，3，4 )；
listlists=permute(nums，0 )；
lists.foreach (system.out :3360 println；
}
}
代码理解：数组{ 1，2，3 }的所有数组为： { 1，2，3，2 }、{ 2，1，3 }、{ 3，1，2 }、{ 3，1，2 }
建立{ 1，2，3 }数组，先建立{ 2，3 }数组，再加上1即可，进一步缩小的是建立{3}数组。 数组是指在同一位置一次放置所有不同的数。
那么代码执行
现上可使用交换元素法，比如首个位置和所有元素都交换一遍，不就是全部可能了吗。这样，首个位置所有可能就遍历了一遍，然后在递归完后，恢复(回溯)一下，就是说每次交换都是某一个下标位置，去交换其他所有元素。
再来个全排列的算法实现，代号B，也是使用回溯的思想：
public class Backtrack {
public static void main(String[] args) {
int[] nums = {1,2,3,4};
List track = new LinkedList<>();
List> res = backtrack(nums,track);
System.out.println(res);
}
// 存储最终结果
private static List> result = new LinkedList<>();
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
private static List> backtrack(int[] nums,List track){
// 结束条件
if (track.size() == nums.length){
result.add(new LinkedList<>(track));
return null;
}
for (int i = 0; i < nums.length; i++) {
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
backtrack(nums,track);
// 撤销选择
track.remove(track.size()-1);
}
return result;
}
}
代码解析：对 {1,2,3} 做全排列，先将 List[0] 放入链表，如果链表中存在该元素，就忽略继续，继续放入List[0+1]，同样的，
存在即忽略继续，直到将List中所有元素，无重复的放入链表，这样就完成了一次排列。这个算法的技巧，是利用了链表的
有序性，第一个位置会因为回溯而尝试放入所有的元素，同样，第二个位置也会尝试放入所有的元素。
画出个决策树：
以 {1-3-2} 为例，如果链表第一个位置为1，那第二个位置为 {2,3} 之一，{1}由于属于存在的重复值忽略，
如果第二个位置放了{3}，那第三个位置就是{2}，就得出了一个结果。
我们对比一下以上两个算法实现： 特别注意，算法B是真正的递归吗？有没有缩小计算规模？
时间复杂度计算公式：分支个数 * 每个分支的计算时间
算法A的分支计算只有元素交换，按Arraylist处理，视为O(1)，算法B分支计算包含链表查找为O(N)，
算法A：N！* O(1) ，阶乘级别，耗时不送。
算法B：N^n * O(N) ，指数级别，会爆炸！
我使用10个数全排测试如下(严谨的讲，两者有数据结构不同的影响，并不是说仅有算法上的差异)：
总结：回溯和递归是两种思想，可以融合，也可以单独使用！
全文完！
我近期其他文章：
1 Redis高级应用
2 聊聊算法——BFS和DFS
3 微服务通信方式——gRPC
4 分布式任务调度系统
5 Dubbo学习系列之十八(Skywalking服务跟踪)
只写原创，敬请关注
关于找一找教程网
本站文章仅代表作者观点，不代表本站立场，所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章，希望广大程序员努力学习，让我们用科技改变世界。
[聊聊算法——回溯算法]http://www.zyiz.net/tech/detail-135184.html