代码随想录算法训练营第22天 | 组合总和 分割回文串

39. 组合总和

39. 组合总和 - 力扣（LeetCode）

题目链接/文章讲解：代码随想录

视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili

自己乱写的，回溯的时候没有去掉重复使用的数字

class Solution {List<Integer> group = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();int sum = 0;public void backTracking (int[] candidates,int target){if(sum == target){List<Integer> temp = new ArrayList(group);Collections.sort(temp);for(List<Integer> oneList:result){if(oneList.equals(temp)==true)return;}result.add(new ArrayList(temp));return;}else if(sum > target)return;for(int i = 0;i < candidates.length;i++){group.add(candidates[i]);sum += candidates[i];backTracking(candidates,target);group.remove(group.size() - 1);sum -= candidates[i];}}public List<List<Integer>> combinationSum(int[] candidates, int target) {backTracking(candidates,target);return result;}
}

没有剪枝

剪枝

修改

class Solution {List<Integer> group = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();int sum = 0;public void backTracking (int[] candidates,int target,int startIndex){if(sum == target){result.add(new ArrayList(group));return;}for(int i = startIndex;i < candidates.length;i++){if(candidates[i] + sum > target)break;//排过序，现在已经超过target，说明后面的数已经不需要遍历了group.add(candidates[i]);sum += candidates[i];backTracking(candidates,target,i);group.remove(group.size() - 1);sum -= candidates[i];}}public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//一定要先对数组排序,为了剪枝backTracking(candidates,target,0);return result;}
}

40.组合总和II

40. 组合总和 II - 力扣（LeetCode）

注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。

题目链接/文章讲解：代码随想录

视频讲解：​​​​​​回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II_哔哩哔哩_bilibili

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public void backTracking(int[] candidates,int target,int startIndex,int sum,boolean[] used){if(sum == target){result.add(new ArrayList(path));return;}else if(sum > target)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] == false){//去重操作continue;}path.add(candidates[i]);sum += candidates[i];used[i] = true;backTracking(candidates,target,i + 1,sum,used);//下一层递归path.remove(path.size() - 1);//回溯sum -= candidates[i];used[i] = false;}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {boolean[] used = new boolean[candidates.length];//记录元素是否被使用Arrays.sort(candidates);//必须排序backTracking(candidates,target,0,0,used);return result;}
}

131.分割回文串

131. 分割回文串 - 力扣（LeetCode）

本题较难，大家先看视频来理解 分割问题，明天还会有一道分割问题，先打打基础。

代码随想录

视频讲解：带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！_哔哩哔哩_bilibili

class Solution {List<String> path = new ArrayList<>();List<List<String>> result = new ArrayList<>();public boolean huiwen(String s,int start,int end){while(start < end){if(s.charAt(start) != s.charAt(end))return false;start++;end--;}return true;}public 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(huiwen(s,startIndex,i)){//左闭右闭区间path.add(s.substring(startIndex,i + 1));//已经切过的不能再切}else continue;backTracking(s,i + 1);path.remove(path.size()-1);}}public List<List<String>> partition(String s) {backTracking(s,0);return result;} 
}