39.组合总和
题目链接：力扣
思路
这道题目和77、216的相同点是都是在同一个集合中，不同点是这里面的相加数字是可以重复的，可以重复的时候就要考虑集合中是否包含0，因为可能会造成无限循环
所以每次相加的时候，集合的下标不用向后移动(保证数字重复)，但是也不能一直处于0（保证结果不重复）
组合总和
未剪枝前
class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { backtracking(candidates,target,0,0); return result; } void backtracking (int[] candidates,int target,int sum,int startIndex) { if (sum > target) { return; } if (sum == target) { result.add(new ArrayList(path)); return; } for (int i = startIndex; i < candidates.length; i++) { path.add(candidates[i]); sum += candidates[i]; backtracking(candidates,target,sum,i); sum -= candidates[i]; path.remove(path.size()-1); } } }
这道题目中数组中的元素不是按照从小到大的顺序进行排序，所以想要进行剪枝，首先就需要对数组进行排序
剪枝优化
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); backtracking(candidates,target,0,0); return result; } // sum 统计path的和. 可以不适用sum进行加，可以使用target进行减操作 // startIndex void backtracking (int[] candidates,int target,int sum,int startIndex) { if (sum > target) { return; } if (sum == target) { result.add(new ArrayList(path)); return; } for (int i = startIndex; i < candidates.length; i++) { // 剪枝操作 如果 sum + candidates[i] > target 就终止遍历 if (sum + candidates[i] > target ) { break; } path.add(candidates[i]); sum += candidates[i]; backtracking(candidates,target,sum,i); sum -= candidates[i]; path.remove(path.size()-1); } } }
40.组合总和II
题目链接：力扣
思路
39.组合总和 一个集合，集合中的无重复元素，求和时元素可以重复选取
40.组合总数|| 一个集合，集合中有重复元素，求和时集合中的每个数字只能出现一次
216.组合总数||| 集合[1,9] 集合中无重复元素，求和时每个数字只能出现一次
使用39的方法写之后，就会发现，这道题目是需要去重的，怎么去重就是这道题目的关键
基本思路是使用过的元素就不再使用了
按照代码随想录中的说法，这里是树层去重，例如例子排序后是[1,1,2,5,6,7,10]，第一个1组合后面的结果，第二个1也是会进行组合的，所以第二个1的结果肯定是和第一个1的重复的
首先要对数组进行排序，排序就是为了让相邻的元素放在一起
used的方法
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过，避免在树枝上删除相同的元素
used[i - 1] == false，说明同一树层candidates[i - 1]使用过，避免在树层上使用相同的元素
组合总和||
class Solution { List<Integer> path = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); 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,0); return result; } void backtracking (int[] candidates, int target, int sum, int startIndex) { // 终止条件 if (sum == target) { result.add(new ArrayList(path)); return; } 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; } used[i] = true; sum += candidates[i]; path.add(candidates[i]); backtracking(candidates,target,sum,i + 1); used[i] = false; sum -= candidates[i]; path.remove(path.size() - 1); } } }
131.分割回文串
题目链接：力扣
思路
感觉所有的知识都总和起来了，算法真的就在于灵活
分割回文串，首先用到了判断字符串是否是回文串的问题，这个比较简单，关键在于怎么对字符串进行分割，原理和组合是一样的
使用startIndex来进行分割，在分割好之后就进行判断，如果合适就添加到结果集合中，如果不合适就跳过这层循环
分割回文串
class Solution { List<String> path = new ArrayList<>(); List<List<String>> result = new ArrayList<>(); public List<List<String>> partition(String s) { backtracking(s,0); return result; } // 回溯函数 void backtracking(String s, int startIndex) { // 终止条件 if (startIndex >= s.length()) { result.add(new ArrayList(path)); return; } // 单层递归的逻辑 for (int i = startIndex; i < s.length(); i++) { // 如果切割下来的字符串是回文串，就添加到集合中，如果不是，这个循环就可以跳过了 if (isPalindrome(s,startIndex,i)) { String str = s.substring(startIndex,i + 1); path.add(str); } else { continue; } backtracking(s,i + 1); path.remove(path.size() - 1); } } // 判断回文串 boolean isPalindrome(String s,int startIndex, int end) { for (int i = startIndex, j = end; i < j; i++,j--) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; } }
