39. 组合总和
题目链接：39. 组合总和
与组合问题类似，关键是理解startIndex的作用，它是控制每组内部，每个元素的选择，如果传入的是i，则组内可重复并且组间不重复，为什么？因为外部有for循环会控制i一直自增前进，然后还有回溯操作，之前被选过的数字在回溯之后是不会再被选择了。下面是没有剪枝之后的代码。
代码1.0：
class Solution {// 1. 不剪枝版本，2ms通过List<Integer> temp = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates, target, 0);return result;}public void backtracking(int[] candidates, int target, int startIndex) { if(target < 0) { // 必须放在外面，因为小于零而退出的，通过回溯来让数据恢复return;} if(target == 0) {result.add(new ArrayList<>(temp));return;}for(int i = startIndex; i < candidates.length; i++) {target -= candidates[i];temp.add(candidates[i]); backtracking(candidates,target, i);// 起始位置传入i，确保数字可以重复选，但是每组不重复 temp.remove(temp.size() - 1);// 回溯，把导致target小于零的数去掉target += candidates[i];}}
}剪枝其实直接放在每次的for循环中，如果目标值减去下一个值已经不满足条件（小于0），则直接跳过下面这个值。而这样，也就少了一个终止条件了，下面是剪枝之后的代码。
代码2.0（剪枝版本）：
class Solution {// 2. 剪枝之后的版本，1ms通过List<Integer> temp = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates, target, 0);return result;}public void backtracking(int[] candidates, int target, int startIndex) {if(target == 0) {result.add(new ArrayList<>(temp));return;}for(int i = startIndex; i < candidates.length; i++) {if(target - candidates[i] < 0) { // 如果减的这个已经小于0，那就没必要加入集合了，直接遍历集合的下一个元素continue;}target -= candidates[i];temp.add(candidates[i]); // 要加入之后再判断，因为不符合的部分会在回溯部分删除掉backtracking(candidates,target, i);temp.remove(temp.size() - 1);target += candidates[i];}}
}40.组合总和II
题目链接：40. 组合总和 II
这题又涉及一个经典问题：“去重”，这里我还是更偏向于先排序之后的去重操作，我自认为更好理。首先这道题是组内不可重复，所以递归时要传i + 1给startIndex，而何时去重呢？排序之后相同元素都在一起，当找到一个满足条件的组合之后，在回溯的地方判断去重：即，满足条件的下一个元素是否和当前满足条件的最后一个元素相同，如果是，则跳过（用一个while循环）。
代码：
class Solution {List<Integer> temp = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);// 先排序，把相同的元素放在一起，方便去重backtracking(candidates, target, 0);return result;}public void backtracking(int[] candidates, int target, int startIndex) {if(target == 0) {result.add(new ArrayList<>(temp));return;}for(int i = startIndex; i < candidates.length; i++) {if(target - candidates[i] < 0) { // 剪枝，有了这一步，在外面的循环就可以少一个退出条件了，因为达到退出条件的，只有符合条件的结果集了continue;}target -= candidates[i];temp.add(candidates[i]);backtracking(candidates, target, i + 1);target += candidates[i];temp.remove(temp.size() - 1);// 回溯之后，为了保证下一次取的数字不重复，一直移动i，便能确保去重，注意要先控制i + 1小于数组大小，否则会出现空指针异常while(i + 1< candidates.length && candidates[i + 1] ==candidates[i]) {i++;}}}
}131.分割回文串
这道题的关键在于怎么切割。而对于Java，切割的方式还是挺多的，下面一一介绍。
1. 用String类存储每一次新的子穿开头，用+来拼接
代码1.0：
class Solution {List<String> temp = new ArrayList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return result;}private void backtracking(String s, int startIndex) {if(startIndex > s.length() - 1) {result.add(new ArrayList<>(temp));return;}String str = "";for(int i = startIndex; i < s.length(); i++) {// System.out.println(str + s.charAt(i));str += s.charAt(i);if(!isHui(str)) {continue;}temp.add(str);// System.out.println(temp.toString());backtracking(s, i + 1);temp.remove(temp.size() - 1);}}public boolean isHui(String s) {int left = 0;int right = s.length() - 1;while(left < right) {if(s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}
}用时最慢，需要17ms
2. 用StringBuilder类自带方法来处理拼接操作
代码2.0：
class Solution {// 2.0 用StringBuilder类的拼接方法比用加法拼接更高效List<String> temp = new ArrayList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return result;}private void backtracking(String s, int startIndex) {if(startIndex > s.length() - 1) { // 传入的起始下标超过字符串最后一个元素时，说明切割结束，可以返回结果了result.add(new ArrayList<>(temp));return;}StringBuilder str = new StringBuilder(); // 每次循环都定义一个新的容器来获取切割的字符串for(int i = startIndex; i < s.length(); i++) {str.append(s.charAt(i)); // 用字符串拼接来获取后面的子串if(!isHui(str.toString())) { // 不是回文的字符串就不加入到temp中，等待下一次拼接，成为回文穿之后再加入continue;}temp.add(str.toString());backtracking(s, i + 1); // 切割的本质其实是for循环中i的移动，与递归调用i + 1（调用i+1还有个作用是防止组间重复的出现）temp.remove(temp.size() - 1);}}public boolean isHui(String s) {int left = 0;int right = s.length() - 1;while(left < right) {if(s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}
}
这个速度也只是快在拼接上，但是由于判断是回文串时，要转化为String类型，所以还是没有达到最快，用时11ms
3. 用String类自带切割方法
代码3.0：
class Solution {List<String> temp = new ArrayList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return result;}private void backtracking(String s, int startIndex) {if(startIndex > s.length() - 1) {result.add(new ArrayList<>(temp));return;}String str = "";for(int i = startIndex; i < s.length(); i++) {str = s.substring(startIndex, i + 1);if(!isHui(str)) {continue;}temp.add(str);backtracking(s, i + 1);temp.remove(temp.size() - 1);}}public boolean isHui(String s) {int left = 0;int right = s.length() - 1;while(left < right) {if(s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}
}直接是String类自带方法，用时最快：8ms!
