夸父追日：第七章回溯算法part02

今日收获：组合总和，组合总和Ⅱ，分割回文串

代码随想录：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

1. 组合总和

题目链接：39. 组合总和 - 力扣（LeetCode）

思路：和216. 组合总和 III - 力扣（LeetCode）很像，不同之处在于可以重复选择当前元素，所以递归时start不用+1

方法：

java">class Solution {List<Integer> path=new ArrayList<>();List<List<Integer>> result=new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {// 先进行排序Arrays.sort(candidates);back(candidates,target,0);return result;}public void back(int[] candidates,int target,int start){// 终止if (target==0){result.add(new ArrayList<>(path));return;}for (int i=start;i<candidates.length;i++){if ((target-candidates[i])<0){ // 提前剪枝return;}path.add(candidates[i]);target-=candidates[i];back(candidates,target,i);path.removeLast();target+=candidates[i];}}
}

总结：

1. 集合中元素可以不断重复，递归中的参数start不加1，表示当前元素还可以在下一层中选

2. 组合中的元素可以无限多，没有k个限制，for循环终止条件是集合的长度（不再有个数限制的剪枝了）

3. 求组合总和时可以利用总和大小提前剪枝，再判断要不要选择当前元素（前提：数组已经排好序了，否则当前和大于总和，不能说明之后就没有更小的元素了）

2. 组合总和Ⅱ

题目链接：40. 组合总和 II - 力扣（LeetCode）

思路：去重的逻辑：同一层不能选一样的（就是for循环中if判断的逻辑），否则结果一样；但是同一个路径中可以选不同位置的相同元素

方法：

java">class Solution {List<Integer> path=new ArrayList<>();List<List<Integer>> result=new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {// 标记选择的数字是否在同一层使用过int[] used=new int[candidates.length];for (int i=0;i<candidates.length;i++){used[i]=0;}Arrays.sort(candidates);back(candidates,target,0,used);return result;}public void back(int[] candidates,int target,int start,int[] used){if (target==0){  // 终止result.add(new ArrayList<>(path));return;}for (int i=start;i<candidates.length;i++){if (i>0&&candidates[i]==candidates[i-1]&&used[i-1]==0){continue;}if ((target-candidates[i])<0){  // 剪枝return;}path.add(candidates[i]);target-=candidates[i];used[i]=1;back(candidates,target,i+1,used);path.removeLast();target+=candidates[i];used[i]=0;}}
}

总结：使用used数组是为了区分究竟在同一层还是同一条路径上选取相同的元素，如果前一个相同元素已经使用过，那么是同一树枝上；如果前一个相同元素还没有使用过，说明是在同一层上。

3. 分割回文串

题目链接：131. 分割回文串 - 力扣（LeetCode）

思路：第一次选择第一个字母，判断是否是回文串，如果是添加到结果集中，如果不是就切割当前字符后面的字符串；后面的字符串切割完成后，StringBuilder添加第二个字符，相当于切割线这次从第二个字符开始切割。注意每次都要传入一个新的StringBuilder对象，表明只有第一次的切割线不断移动位置，后面都是从第一个字符开始切割。

方法：

java">class Solution {List<List<String>> result=new ArrayList<>();List<String> path=new ArrayList<>();public List<List<String>> partition(String s) {back(s,0,new StringBuilder());return result;}public void back(String s,int cut,StringBuilder sb){// 终止if (cut==s.length()){result.add(new ArrayList<>(path));return;}for (int i=cut;i<s.length();i++){sb.append(s.charAt(i));if (isHui(sb.toString())){path.add(sb.toString());back(s,i+1,new StringBuilder());path.removeLast();}}}// 判断字符串是否回文public boolean isHui(String str){int len=str.length();for (int i=0,j=len-1;i<j;i++,j--){if (str.charAt(i)!=str.charAt(j)){return false;}}return true;}
}

总结：

1. 切割问题可以抽象为组合问题，只要一步步确定分割线

2. 判断回文子串可以先根据字符串长度剪枝，然后利用相向双指针法（相反方向）

3. 当切割线移动到右边已经没有字符时，收集结果并返回