代码随想录算法训练营第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;
    } 
}