)
回溯
1.理论基础
递归下面就是回溯。
回溯搜索法，其实是一个纯暴力搜索。
回溯解决的问题：组合问题，切割问题，子集问题，排列问题，棋盘问题
递归函数没有返回值，终止条件+单层搜索逻辑（for循环处理集合元素）+回溯
void backtracking(/*参数*/) { if (/*终止条件*/) { //存放结果; return; } for (/*选择：本层集合中元素（树中节点孩子的数量就是集合的大小）*/) { //处理节点; //backtracking(路径，选择列表); // 递归 //回溯，撤销处理结果 } }2.组合问题77. 组合 - 力扣（LeetCode）
递归函数参数 返回值
终止条件
单层递归逻辑
classSolution{List<List<Integer>>ans=newArrayList<>();voidbackTrace(List<Integer>tmp,inti,intn,intk){if(tmp.size()==k)//终止条件{ans.add(newArrayList<>(tmp));return;}for(intj=i;j<=n;j++){tmp.add(j);backTrace(tmp,j+1,n,k);tmp.remove(tmp.size()-1);}}publicList<List<Integer>>combine(intn,intk){//其实就是从大到小 然后每次pop 再进他后面的List<Integer>tmp=newArrayList<>();backTrace(tmp,1,n,k);returnans;}}3.组合问题的剪枝操作
上面那个题目可以进行剪枝，这样往下的深度就不会那么多了。这样就是一个树里可以走到所有值
j<=n-(k-tmp.size())+1*4.组合总和216. 组合总和 III - 力扣（LeetCode）
classSolution{List<List<Integer>>ans=newArrayList<>();voidbacktracing(List<Integer>tmp,inti,intk,intn){if(tmp.size()==k){if(n==0)ans.add(newArrayList<>(tmp));//不管是不是想要的值都要进行返回了 不然不会popreturn;}//进行剪枝for(intj=i;j<10&&j<=n;j++){tmp.add(j);backtracing(tmp,j+1,k,n-j);tmp.remove(tmp.size()-1);}}publicList<List<Integer>>combinationSum3(intk,intn){List<Integer>tmp=newArrayList<>();backtracing(tmp,1,k,n);returnans;}}5.电话号码的字母组合17. 电话号码的字母组合 - 力扣（LeetCode）
classSolution{//模板privatestaticfinalString[]MAPPING=newString[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};privatevoiddfs(List<String>ans,inti,char[]digits,char[]path){if(i==digits.length){//到达终止条件ans.add(newString(path));return;}Stringletters=MAPPING[digits[i]-'0'];for(charc:letters.toCharArray()){path[i]=c;dfs(ans,i+1,digits,path);//往后继续递归}}publicList<String>letterCombinations(Stringdigits){intn=digits.length();if(n==0){returnList.of();//直接返回空}List<String>ans=newArrayList<>();//看一下是怎么声明char数组的char[]path=newchar[n];dfs(ans,0,digits.toCharArray(),path);returnans;}}*6.组合总和39. 组合总和 - 力扣（LeetCode）
相较于之前，元素可以重复使用，所以剩余集合就是可以一直往下。但是要排除掉大于的东西。
classSolution{List<List<Integer>>ans;List<Integer>path;publicvoiddfs(inti,inttarget,int[]candidates){if(i==candidates.length){return;//现在已经全部弄完了}if(target==0){//已经到达最终结果了ans.add(newArrayList(path));return;}//可以直接不选dfs(i+1,target,candidates);//剪枝进行选择if(target-candidates[i]>=0){path.add(candidates[i]);//因为可以重复选择 所以还是从当前元素开始dfs(i,target-candidates[i],candidates);path.remove(path.size()-1);//回退}}publicList<List<Integer>>combinationSum(int[]candidates,inttarget){this.ans=newArrayList<>();this.path=newArrayList<>();dfs(0,target,candidates);returnans;}}*7.组合总和240. 组合总和 II - 力扣（LeetCode）
classSolution{List<List<Integer>>ans=newArrayList<>();List<Integer>path=newArrayList<>();//只能出现一次 所以每次只能往后加publicvoiddfs(inti,inttarget,int[]candidates){if(target==0){ans.add(newArrayList<>(path));return;}//开始往后进行for(intj=i;j<candidates.length;j++){//剪枝if(target-candidates[j]>=0){System.out.println(i);//排除掉重复的部分if(j>i&&candidates[j]==candidates[j-1]){continue;}//可以继续往下进行操作path.add(candidates[j]);dfs(j+1,target-candidates[j],candidates);path.remove(path.size()-1);}}}publicList<List<Integer>>combinationSum2(int[]candidates,inttarget){Arrays.sort(candidates);dfs(0,target,candidates);returnans;}}*8.分割回文串131. 分割回文串 - 力扣（LeetCode）
先判断前面的对不对 再往后继续加
classSolution{List<List<String>>ans=newArrayList<>();List<String>path=newArrayList<>();publicbooleanisP(Strings,inta,intb){while(a<b){if(s.charAt(a++)!=s.charAt(b--)){returnfalse;}}returntrue;}publicvoidbackTracing(inti,Strings){//切割完成if(i==s.length()){ans.add(newArrayList<>(path));return;}for(intj=i;j<s.length();j++){if(isP(s,i,j)){path.add(s.substring(i,j+1));//分割backTracing(j+1,s);path.removeLast();}}}publicList<List<String>>partition(Strings){backTracing(0,s);returnans;}}9.复原IP地址93. 复原 IP 地址 - 力扣（LeetCode）
classSolution{//其实就是分割成四个有效的数字List<String>ans=newArrayList<>();//记录数的集合List<List<Integer>>res=newArrayList<>();List<Integer>path=newArrayList<>();//判断加上当前数是否能组成新的合法数publicbooleanisValid(Strings,intstart,intend){intlen=end-start+1;if(len<1||len>3){returnfalse;}//第一个数不能为0if(len>1&&s.charAt(start)=='0'){returnfalse;}intnum=Integer.parseInt(s.substring(start,end+1));returnnum<=255;}publicvoidbackTracing(inti,Strings){if(path.size()==4){if(i==s.length()){res.add(newArrayList<>(path));}return;}if(s.length()-i>(4-path.size())*3)//剩余字符过多{return;}if(s.length()-i<(4-path.size()))//过少{return;}for(intj=i;j<s.length()&&j<i+3;j++){//继续叠加if(isValid(s,i,j)){//parseIntintnum=Integer.parseInt(s.substring(i,j+1));path.add(num);backTracing(j+1,s);path.removeLast();}}}publicList<String>restoreIpAddresses(Strings){if(s.length()<4||s.length()>12){returnans;}backTracing(0,s);for(List<Integer>nums:res){//里面还是一个数的数组StringBuildersb=newStringBuilder();for(inti=0;i<4;i++){sb.append(nums.get(i));// 每两个元素之间加 "."（最后一个元素后不加）if(i!=nums.size()-1){sb.append(".");}}ans.add(sb.toString());}returnans;}}10.子集78. 子集 - 力扣（LeetCode）
classSolution{List<List<Integer>>ans=newArrayList<>();List<Integer>path=newArrayList<>();publicvoidbackTracing(intidx,int[]nums){ans.add(newArrayList<>(path));//不管怎么样上来就先直接放进去for(inti=idx;i<nums.length;i++){path.add(nums[i]);backTracing(i+1,nums);path.remove(path.size()-1);}}publicList<List<Integer>>subsets(int[]nums){backTracing(0,nums);returnans;}}该死的回溯…
