代码随想录算法训练营day26|39. 组合总和、40. 组合总和||、8.分割回文串

本文主要是介绍代码随想录算法训练营day26|39. 组合总和、40. 组合总和||、8.分割回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

39. 组合总和

由题意可知，数组中的每一个数都可以重复相加，因此我们在绘制树形图的时候，每次取完某一个数，下一次回溯的时候还可以用该数，比如2、3、6，每次取完2，候选还剩2、3、6。而最后答案也确实是2、2，所以2每次取完不能排除。
另外对于存储满足条件结果的path，每次从纵向的回溯过程出来之后，要将这一层回溯加进去的值减掉给横向的循环的下一个值腾出空间，一边进入下一个值的回溯。同时要给一个sum的值记录和。

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();ArrayList<Integer> path = new ArrayList<Integer>();public List<List<Integer>> combinationSum(int[] candidates, int target) {if(candidates.length == 0 || candidates == null) return res;backTracking(candidates,target,0,0);return res;}public void backTracking(int[] candidates, int target,int sum,int startIndex){if(sum > target) return;if(sum == target) res.add(new ArrayList<Integer>(path));//循环for(int i = startIndex;i < candidates.length;i++){sum += candidates[i];path.add(candidates[i]);backTracking(candidates,target,sum,i);sum -= candidates[i];path.remove(path.size()-1);}}
}

40. 组合总和||

我觉得这道题目卡个2讲的已经够好了，多看几遍理解透彻就行。主要就是需要对candidates进行排序，然后理解去重的条件为什么是：

      if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {continue;}

最后的代码是：
其中：used是用来记录该位置的candidates的值是否被用过

class Solution {List<List<Integer>> res = new ArrayList<List<Integer>>();ArrayList<Integer> path = new ArrayList<Integer>();int sum = 0;boolean[] used;public List<List<Integer>> combinationSum2(int[] candidates, int target) {used = new boolean[candidates.length];Arrays.fill(used, false);Arrays.sort(candidates);backTracking(candidates,target,0);return res;}public void backTracking(int[] candidates, int target,int startIndex){if(sum == target) res.add(new ArrayList<Integer>(path));for(int i = startIndex;i < candidates.length;i++){if(sum + candidates[i] > target){break;}// 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {continue;}sum += candidates[i];used[i] = true;path.add(candidates[i]);backTracking(candidates,target,i+1);sum -= candidates[i];used[i] = false;path.remove(path.size()-1);}}
}

8.分割回文串

class Solution {List<List<String>> res = new ArrayList<List<String>>();ArrayList<String> path = new ArrayList<String>();public List<List<String>> partition(String s) {backTracking(s,0);return res;}public void backTracking(String s,int startIndex){//如果起始值到达字符串末尾，结束递归if(startIndex >= s.length()){res.add(new ArrayList<>(path));return;}for (int i = startIndex; i < s.length(); i++) {if(judgeHuiWen(s,startIndex,i)){path.add(s.substring(startIndex,i+1));}else{continue;//有一个子字符串不是回文字符串就没有必要进行回溯了}//如果现层的子字符串为回文的，继续回溯backTracking(s,i+1);//i往下一位，继续回溯//回溯path.remove(path.size()-1);}}public boolean judgeHuiWen(String s,int startIndex,int endIndex){while(startIndex <= endIndex){if(s.charAt(startIndex) != s.charAt(endIndex)) return false;startIndex++;endIndex--;}return true;}
}