算法训练营day27(回溯算法03:组合总和,组合总和2,分割回文串)

第七章 回溯算法part03● 39. 组合总和
● 40.组合总和II
● 131.分割回文串详细布置 39. 组合总和 本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html 
视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ  40.组合总和II 本题开始涉及到一个问题了：去重。注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。 题目链接/文章讲解：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html   
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A131.分割回文串  本题较难，大家先看视频来理解 分割问题，明天还会有一道分割问题，先打打基础。 https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html  
视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6  往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl

day27

组合总和

 class Solution {List<List<Integer>> result = new ArrayList();LinkedList<Integer> path = new LinkedList<>();int sum = 0;//组合问题,用回溯,回溯函数里面有for循环,for循环里面有回溯函数;//回溯宽度:for写每次分支的宽度,从index到最后;//回溯深度:通过sum去判断public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracting( candidates, target, 0);return result;}private void backtracting(int[] candidates, int target, int index){  if(sum > target) return;if(sum == target) {result.add(new ArrayList(path));}//回溯深度结束for( int i = index; i < candidates.length; i++){//每次分支的宽度path.add(candidates[i]);sum +=candidates[i];backtracting(candidates,target,i);//元素可以重复,不用+1sum -=candidates[i];path.removeLast();}}}​//剪枝class Solution {List<List<Integer>> result = new ArrayList();LinkedList<Integer> path = new LinkedList<>();int sum = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//排序backtracting( candidates, target, 0);return result;}private void backtracting(int[] candidates, int target, int index){  if(sum > target) return;if(sum == target) {result.add(new ArrayList(path));}for( int i = index; i < candidates.length && sum + candidates[i] <= target; i++){//如果回溯宽度上的下一个分支>target,直接退出这次for循环path.add(candidates[i]);sum +=candidates[i];backtracting(candidates,target,i);sum -=candidates[i];path.removeLast();}}}

---

组合总和2

 class Solution {List<List<Integer>> result = new ArrayList<>();//保存结果LinkedList<Integer> path = new LinkedList<>();//结果集中的每一个集合,用linkedlist方便随后一个元素弹出,便于回溯处理int sum = 0;//用于判断回溯深度什么时候停止boolean[] used;//控制树枝不去重public List<List<Integer>> combinationSum2(int[] candidates, int target) {//本题关键在于区分树层去重和树枝去重,target=8,{1,7}和{1,7}不能同时存在,树层去重我们在for循环下面(回溯宽度方向上)做一个判断;//树枝方向上不需要去重,我们用used[]数组去标记此时到底是在树枝方向上还是树层方向上//回溯深度上的结束我们用sum == target以及sum > target去控制//回溯宽度上我们用i遍历到candidates.length去控制Arrays.sort(candidates);//排序,方便去重used = new boolean[candidates.length];backtracking(candidates,target,0);//index用于控制for循环(回溯宽度方向的开始和停止)return result;}private void backtracking(int[] candidates, int target, int index){//回溯深度控制if(sum > target) return;if(sum == target) {result.add(new ArrayList(path));//收货return;}//回溯宽度控制for(int i = index; i < candidates.length; i++){if( i > 0 && candidates[i] == candidates[i-1] && used[i-1] != true) continue;//树层去重,树枝不去重//注意是continue而不是return或者break,只跳过这一个重复数就行,后面非重复元素还要继续判断的path.add(candidates[i]);//加到可能的路径中sum += candidates[i];used[i] = true;backtracking(candidates, target, i+1);//进入树枝(下一层回溯),里面的判断都是used[i - 1]为trueused[i] = false;//回溯到树层sum -=candidates[i];path.removeLast();}}}

---

分割回文串

 class Solution {LinkedList<String> path = new LinkedList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {//分割回文子串和组合问题本质是一样的,只不是组合问题是选择每次添加的元素的index,而回文串是选择每次子串的结束位置的indexbacktracking(s, 0);return result;}private void backtracking(String s, int index){if( index == s.length()) {result.add(new ArrayList<>(path));//path类型转换return;//结束深度方向的回溯,回文串合法性交给每次index划分后去判断}// 遍历所有的子串for (int i = index; i < s.length(); i++) {String substring = s.substring(index, i+1 ); // 提取子串,左闭右开if (!check(s, index, i)) continue;  // 如果不是回文串，跳过           // 添加回文子串到路径path.add(substring);// 继续回溯，处理下一个子串backtracking(s, i + 1);          // 回溯，移除当前子串path.removeLast();}}private boolean check( String s, int left,int right){while(left < right){if(s.charAt(left) == s.charAt(right)){left++;right--;}else return false;}return true;}}//也可以不用s.substring(),可以每次进入backtricking就new一个StringBuilder

---

小结:

回溯就是深度控制＋宽度控制,进入回溯函数之后先判断是不是深度要结束了(不进入下一层回溯函数),然后用for循环控制宽度,如果满足条件就收集起来1,然后进入下一层回溯函数,回溯函数出来之后要把收集的1再抛弃出去,这样才能进入下一个大分支.

感受:

参考了一个用c++做算法题的大佬的做题方式,写了很多注释,也加入了自己的小结,独立把代码写出来后对回溯的理解更深了.还是要慢慢做题,写上自己的理解,做一道题有一道题的收获.

---

感谢大佬们分享:

代码随想录-算法训练营day27【回溯算法03：组合总和、分割回文串】-CSDN博客

代码随想录算法训练营第二十三天|Day23 回溯算法-CSDN博客