算法笔记：回溯算法

回溯法理论基础


「回溯是递归的副产品，只要有递归就会有回溯」，所以回溯法也常常和二叉树遍历，深度优先搜刮混在一起，因为这两种方式都是用了递归。
回溯法就是暴力搜刮，并不是什么高效的算法，最多再剪枝一下。
回溯算法能办理如下问题：

• 组合问题：N个数内里按一定规则找出k个数的聚集
  
• 排列问题：N个数按一定规则全排列，有几种排列方式
  
• 切割问题：一个字符串按一定规则有几种切割方式
  
• 子集问题：一个N个数的聚集里有多少符合条件的子集
  
• 棋盘问题：N皇后，解数独等等
  

回溯算法模板：

1. //一定要分成横纵两个方面思考回溯
2. void backtracking(参数) {
3.     if (终止条件) {
4.         存放结果;
5.         return;
6.     }
8.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {//注意i=0,i=start的区别
9.         处理节点;
10.         backtracking(路径，选择列表); // 递归  注意(i)和(i++)的区别  后面会懂
11.         回溯，撤销处理结果 这一步很重要
12.     }
13. }

复制代码

组合问题

组合问题

（组合问题就是将若干个数组合在一起构成答案）
在文中开始的时间给大家列举k层for循环例子，进而得出都是同样是暴利解法，为什么要用回溯法！
「此时大家应该深有体会回溯法的魅力，用递归控制for循环嵌套的数目！」

本题搜刮的过程抽象成树形结构如下：

可以直观的看出其搜刮的过程：「for循环横向遍历，递归纵向遍历，回溯不停调解结果集」，这个理念贯穿整个回溯法系列，也是我做了很多回溯的题目，不停摸索其规律才总结出来的。优化回溯算法只有剪枝一种方法即：「已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没故意义了，直接剪掉」，如图：

代码：

1. class Solution {
2.     List<List<Integer>> R=new ArrayList<>();
3.     LinkedList<Integer> result=new LinkedList<>();
4.     Set<String> set=new HashSet<>();
5.     public List<List<Integer>> combinationSum(int[] candidates, int target) {   
6.            //
7.         hui(candidates,0,target);
8.         return R;
9.     }
12.     public List<Integer> hui(int [] arr,int start,int target){
13.         if(target<0){
14.             return null;
15.         }
17.         if(target==0){ //注意需要去重
18.             Object [] sort=result.toArray();
19.             int [] ins=new int[sort.length];
20.             int y=0;
21.             for(Object o:sort){
22.                 ins[y]=Integer.parseInt(String.valueOf(sort[y]));
23.                 y++;
24.             }
26.             Arrays.sort(ins);
27.             String key=Arrays.toString(ins);
28.             if(set.contains(key)){
29.                 return null;
30.             }else{
32.                 R.add(new ArrayList<>(result));
33.                 set.add(key);
34.             }
35.             return null;
36.         }
37.         int t=target;
39.         for(int i=start;i<arr.length;i++){
40.             int value=arr[i];
41.             result.add(value);
42.             target=target-value;
43.             hui(arr,start,target);
44.             result.removeLast();
45.             target=t;
46.         }
49.         return null;
51.     }
52. }

复制代码

子集问题

讲简单一点就是边递归边存值的问题。
子集问题（一）

在回溯算法：求子集问题！中解说了子集问题，「在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果」。

认清这个本质之后，本日的题目就是一道模板题了。
「本题其实可以不必要加终止条件」，因为startIndex >= nums.size()，本层for循环本来也结束了，本来我们就要遍历整颗树。
有的同砚可能担心不写终止条件会不会无穷递归？
并不会，因为每次递归的下一层就是从i+1开始的。
代码：

1. class Solution {
2.     List<List<Integer>> result=new ArrayList<>(); //总结果
3.     LinkedList<Integer> path=new LinkedList<>(); //每一层路径
4.     public List<List<Integer>> subsets(int[] nums) {
5.         //选当前元素与不选当前元素
6.         dfs(nums,0);
7.         return result;
8.     }
9.    
10.     public void dfs(int [] arr,int start){
11.                 //将当前路径加入到结果中
12.         result.add(new ArrayList<>(path));
13.         if(start>=arr.length){
14.             return;
15.         }
16.         //然后从start位置开始往后处理
17.         for(int i=start;i<arr.length;i++){
18.             //将start位置添加进去
19.             path.add(arr[i]);
20.             dfs(arr,i+1); //从下一个开始
21.             //到此上一个节点已经递归完毕 然后需要将节点移除
22.             path.removeLast();
23.         }
24.     }
26. }

复制代码

子集问题（二）

本题思绪主要就是确定切割思绪、然后判定是否是回文，当所有子串都是回文是代表有用结果其实切割问题雷同组合问题。

实当代码：

1. class Solution {
3.     List<List<String>> R=new ArrayList<>();
4.     LinkedList<String> result=new LinkedList<>();
5.     public List<List<String>> partition(String s) {
7.         hui(s,0);
8.         return R;
11.     }
12.     //其实就是几种切割方式
13.     //如何判断已经分割完毕呢？
14.     //判断是否有剩余元素-> 即每次分割后传入进来的s是否为空字符串
15.     public void hui(String s,int start){ //start表示当前截取的索引位置
16.         if(s.equals("")){ //已经截取完毕
17.          //关键是当前截取的组合如何判断是回文串
18.          //要么就是单个元素  要么就是只有一个元素比如 a 或者aaaaa
19.         //从链表中一一取出
20.         for(String r:result){
21.            boolean f=change(r); //判断当前组合的元素是否是回文串 必须每个子串都是回文串
22.             if(f==false){ //只要有一个不是 则当前结果作废
23.                 return;
24.             }
25.         } //走到这代表都是符合的 将当前结果添加到结果中
26.         R.add(new ArrayList<>(result));
27.         return;
28.         }
29.         
30.         //默认从0开始截取
31.         for(int i=0;i<s.length();i++){
32.             //以aab为例  先截a   然后截取aa  然后就是aab                                       
33.             String son=s.substring(0,i+1);//注意左开右闭  //那么 剩余部分递归到下一个子树
34.             String next=s.substring(i+1,s.length());//下一个递归的字符串
36.             result.add(son);
37.             hui(next,i);
38.             result.removeLast();
39.         }
40.     }
42.     public boolean change(String s){ //判断是否是回文
44.         if(s.length()==1){ //单个字母一定是回文  //或者前后对称 aba
45.             return true;
46.         }
48.         boolean flag=true;
50.         char [] arr=s.toCharArray();
51.         char [] n=new char[arr.length];
52.         char [] la=new char[arr.length];
55.        // char first=arr[0];
56.        //从前往后
57.         int j=0;
58.         for(char c:arr){
59.             n[j]=arr[j];
60.             j++;
61.         }
62.         //从后往前
63.         int qian=0;
64.         int l=arr.length-1;
65.         for(char a:arr){
66.             la[qian]=arr[l];
67.             qian++;
68.             l--;
69.         }
71.         String q=Arrays.toString(n);
72.         String h=Arrays.toString(la);
73.         if(!q.equals(h)){
74.             flag=false;
75.         }
76.         //对于aba这种情况 从前往后遍历和从后往前遍历应该是一样的
77.         return flag;
79.     }
80. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。