算法笔记：回溯算法
回溯法理论基础「回溯是递归的副产品，只要有递归就会有回溯」，所以回溯法也常常和二叉树遍历，深度优先搜刮混在一起，因为这两种方式都是用了递归。
回溯法就是暴力搜刮，并不是什么高效的算法，最多再剪枝一下。
回溯算法能办理如下问题：
[*]组合问题：N个数内里按一定规则找出k个数的聚集
[*]排列问题：N个数按一定规则全排列，有几种排列方式
[*]切割问题：一个字符串按一定规则有几种切割方式
[*]子集问题：一个N个数的聚集里有多少符合条件的子集
[*]棋盘问题：N皇后，解数独等等
回溯算法模板：
//一定要分成横纵两个方面思考回溯
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {//注意i=0,i=start的区别
处理节点;
backtracking(路径，选择列表); // 递归注意(i)和(i++)的区别后面会懂
回溯，撤销处理结果 这一步很重要
}
} 组合问题
组合问题
（组合问题就是将若干个数组合在一起构成答案）
在文中开始的时间给大家列举k层for循环例子，进而得出都是同样是暴利解法，为什么要用回溯法！
「此时大家应该深有体会回溯法的魅力，用递归控制for循环嵌套的数目！」
https://img-blog.csdnimg.cn/img_convert/6b0948e764c402310a809dda92b39a21.png
本题搜刮的过程抽象成树形结构如下：
https://img-blog.csdnimg.cn/img_convert/5b4828f0601328668bdd7830ce064be2.png
可以直观的看出其搜刮的过程：「for循环横向遍历，递归纵向遍历，回溯不停调解结果集」，这个理念贯穿整个回溯法系列，也是我做了很多回溯的题目，不停摸索其规律才总结出来的。优化回溯算法只有剪枝一种方法即：「已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没故意义了，直接剪掉」，如图：
https://img-blog.csdnimg.cn/img_convert/45ea4609b8bf4d6a678cd8c76836f1e4.png
代码：
class Solution {
List<List<Integer>> R=new ArrayList<>();
LinkedList<Integer> result=new LinkedList<>();
Set<String> set=new HashSet<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//
hui(candidates,0,target);
return R;
}
public List<Integer> hui(int [] arr,int start,int target){
if(target<0){
return null;
}
if(target==0){ //注意需要去重
Object [] sort=result.toArray();
int [] ins=new int;
int y=0;
for(Object o:sort){
ins=Integer.parseInt(String.valueOf(sort));
y++;
}
Arrays.sort(ins);
String key=Arrays.toString(ins);
if(set.contains(key)){
return null;
}else{
R.add(new ArrayList<>(result));
set.add(key);
}
return null;
}
int t=target;
for(int i=start;i<arr.length;i++){
int value=arr;
result.add(value);
target=target-value;
hui(arr,start,target);
result.removeLast();
target=t;
}
return null;
}
} 子集问题
讲简单一点就是边递归边存值的问题。
子集问题（一）
https://img-blog.csdnimg.cn/img_convert/fda4fd464487665d26f61fb09d8928c6.png
在回溯算法：求子集问题！中解说了子集问题，「在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果」。
https://img-blog.csdnimg.cn/img_convert/b1ef386874d86f5e214f52ceb7c462fe.png
认清这个本质之后，本日的题目就是一道模板题了。
「本题其实可以不必要加终止条件」，因为startIndex >= nums.size()，本层for循环本来也结束了，本来我们就要遍历整颗树。
有的同砚可能担心不写终止条件会不会无穷递归？
并不会，因为每次递归的下一层就是从i+1开始的。
代码：
class Solution {
List<List<Integer>> result=new ArrayList<>(); //总结果
LinkedList<Integer> path=new LinkedList<>(); //每一层路径
public List<List<Integer>> subsets(int[] nums) {
//选当前元素与不选当前元素
dfs(nums,0);
return result;
}
public void dfs(int [] arr,int start){
//将当前路径加入到结果中
result.add(new ArrayList<>(path));
if(start>=arr.length){
return;
}
//然后从start位置开始往后处理
for(int i=start;i<arr.length;i++){
//将start位置添加进去
path.add(arr);
dfs(arr,i+1); //从下一个开始
//到此上一个节点已经递归完毕 然后需要将节点移除
path.removeLast();
}
}
} 子集问题（二）
本题思绪主要就是确定切割思绪、然后判定是否是回文，当所有子串都是回文是代表有用结果其实切割问题雷同组合问题。
https://img-blog.csdnimg.cn/img_convert/a769264ca0c20390095cfd13f2b87484.png
https://img-blog.csdnimg.cn/img_convert/a444e09314568a216d49d02c9e40f4b4.jpeg
实当代码：
class Solution {
List<List<String>> R=new ArrayList<>();
LinkedList<String> result=new LinkedList<>();
public List<List<String>> partition(String s) {
hui(s,0);
return R;
}
//其实就是几种切割方式
//如何判断已经分割完毕呢？
//判断是否有剩余元素-> 即每次分割后传入进来的s是否为空字符串
public void hui(String s,int start){ //start表示当前截取的索引位置
if(s.equals("")){ //已经截取完毕
//关键是当前截取的组合如何判断是回文串
//要么就是单个元素要么就是只有一个元素比如 a 或者aaaaa
//从链表中一一取出
for(String r:result){
boolean f=change(r); //判断当前组合的元素是否是回文串 必须每个子串都是回文串
if(f==false){ //只要有一个不是 则当前结果作废
return;
}
} //走到这代表都是符合的 将当前结果添加到结果中
R.add(new ArrayList<>(result));
return;
}
//默认从0开始截取
for(int i=0;i<s.length();i++){
//以aab为例先截a 然后截取aa然后就是aab
String son=s.substring(0,i+1);//注意左开右闭//那么 剩余部分递归到下一个子树
String next=s.substring(i+1,s.length());//下一个递归的字符串
result.add(son);
hui(next,i);
result.removeLast();
}
}
public boolean change(String s){ //判断是否是回文
if(s.length()==1){ //单个字母一定是回文//或者前后对称 aba
return true;
}
boolean flag=true;
char [] arr=s.toCharArray();
char [] n=new char;
char [] la=new char;
// char first=arr;
//从前往后
int j=0;
for(char c:arr){
n=arr;
j++;
}
//从后往前
int qian=0;
int l=arr.length-1;
for(char a:arr){
la=arr;
qian++;
l--;
}
String q=Arrays.toString(n);
String h=Arrays.toString(la);
if(!q.equals(h)){
flag=false;
}
//对于aba这种情况 从前往后遍历和从后往前遍历应该是一样的
return flag;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]