代码随想录算法训练营第二十三天 | 39-组合总和、40-组合总和Ⅱ、131-分割回文串
LeetCode39 组合总和
题目链接：https://leetcode.cn/problems/combination-sum/description/
文章讲解：https://programmercarl.com/0039.组合总和.html
视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ/?vd_source=b989f2b109eb3b17e8178154a7de7a51
需要startIndex来控制for循环的起始位置：如果是一个集合来求组合的话，就需要startIndex；如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex
对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历，完成剪枝
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> records = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backTracking(candidates, target, 0, 0);return result;}public void backTracking(int[] candidates, int target, int sum, int start){if(sum == target){result.add(new ArrayList<>(records));return;}for(int i = start; i < candidates.length; i++){if(sum + candidates[i] > target){break;}records.add(candidates[i]);backTracking(candidates, target, sum + candidates[i], i);records.remove(records.size()-1);}}
}
LeetCode40 组合总和Ⅱ
题目链接：https://leetcode.cn/problems/combination-sum-ii/description/
文章讲解：https://programmercarl.com/0040.组合总和II.html
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A/?vd_source=b989f2b109eb3b17e8178154a7de7a51
本题给的集合是有重复元素的，那么求出来的组合有可能重复，但题目要求不能有重复组合，因此需要去重
组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过，因此分为树枝去重和树层去重
本题要求元素在同一个组合内是可以重复的，但两个组合不能相同，所以要树层去重，树枝不用去重
如果 candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明前一个树枝使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]，此时for循环里就应该做continue的操作，做树层的去重
class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> records = new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);int[] used = new int[candidates.length];backTracking(candidates, target, 0, 0, used);return result;}public void backTracking(int[] candidates, int target, int sum, int start, int[] used){if(sum == target){result.add(new ArrayList<>(records));return;}for(int i = start; i < candidates.length; i++){if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == 0){continue;}if(sum + candidates[i] > target){break;}records.add(candidates[i]);used[i] = 1;backTracking(candidates, target, sum + candidates[i], i+1, used);used[i] = 0;records.remove(records.size()-1);}}
}
LeetCode131 分割回文串
题目链接：https://leetcode.cn/problems/palindrome-partitioning/description/
文章讲解：https://programmercarl.com/0131.分割回文串.html
视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6/?vd_source=b989f2b109eb3b17e8178154a7de7a51
切割问题，也可以抽象为一棵树形结构。递归用来纵向遍历，for循环用来横向遍历，切割线切割到字符串的结尾位置，说明找到了一个切割方法，此时可以发现，切割问题的回溯搜索过程和组合问题的回溯搜索过程是差不多的
本题递归函数参数还需要startIndex作为切割线，切割过的地方，不能重复切割，和组合问题也是保持一致的
在 for (int i = startIndex; i < s.size(); i++) 循环中，我们定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。首先判断这个子串是不是回文，如果是回文，就加入records中，records用来记录切割过的回文子串
判断回文子串，可以使用双指针法，前后往中间遍历
class Solution {List<List<String>> result = new ArrayList<>();List<String> records = new ArrayList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return result;}public boolean isPalindrome(String str){for(int i = 0, j = str.length()-1; i < j; i++, j--){if(str.charAt(i) != str.charAt(j)){return false;}}return true;}public void backTracking(String str, int start){if(start >= str.length()){result.add(new ArrayList<>(records));return;}for(int i = start; i < str.length(); i++){String curStr = str.substring(start, i+1);if(isPalindrome(curStr)){records.add(curStr);backTracking(str, i+1);records.remove(records.size()-1);}}}
}