Leetcode刷题Day26休息&Day27------------------回溯算法

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

Leetcode刷题Day26休息&Day27------------------回溯算法

1. 39. 组合总和

题目链接https://leetcode.cn/problems/combination-sum/
文章讲解https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
视频讲解https://www.bilibili.com/video/BV1KT4y1M7HJ

重点该题没有说要取多少个数并且可以重复。和上题的区别是上题要求了K个元素树的深度是K且不能重复

关于区别的考虑点

有和定义全局变量sum
不知道取多少个数for循环的终止条件是数组的个数几个不重要了sum才重要
可以重复在单层递归逻辑里再调用backtracking()时index不从i+1开始从i开始
剪枝操作在调用方法前先给数组排序在for循环的终止条件如果 sum + candidates[i] > target 就终止遍历

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    int sum=0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates,target,0);
        return result;
    }
    public void backTracking(int[] candidates, int target, int index){
        if(sum == target){
            result.add(new ArrayList<>(path));
            return;
        }
        //剪枝
        for(int i = index;i<candidates.length && sum<target;i++){
           if(sum + candidates[i] > target) break;
           sum+=candidates[i];
           path.add(candidates[i]);
           backTracking(candidates,target,i);
           //回溯记得要给总和减去最后一个数
           int temp = path.getLast();
           sum -= temp;
           path.removeLast();
        }
    }
}

2. 40.组合总和II

题目链接
文章讲解https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
视频讲解https://www.bilibili.com/video/BV12V4y1V73A

重点
与上题的区别是所给的组合里有重复元素但是结果里的组合不能有重复元素----------------》方法要去重当该元素与上一个元素相同时就不能使用了

演变为代码

//与上题的不同去掉一样的元素
if( i > index && candidates[i]==candidates[i-1]) continue;
//与上题的不同不能重复所以要从下一个开始
backTracking(candidates,target, i+1);

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    int sum=0;
    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 index){
        if(sum == target){
            result.add(new ArrayList<>(path));
            return;
        }
    
        //剪枝
        for(int i = index;i<candidates.length && sum<target;i++){
           if(sum + candidates[i] > target) break;
//与上题的不同去掉一样的元素
           if(i > index && candidates[i]==candidates[i-1]) continue;
           
           sum+=candidates[i];
           path.add(candidates[i]);
//与上题的不同不能重复所以要从下一个开始         
           backTracking(candidates,target,i+1);
           //回溯记得要给总和减去最后一个数
           int temp = path.getLast();
           sum -= temp;
           path.removeLast();
        }
    }
}

3. 131.分割回文串

题目链接https://leetcode.cn/problems/palindrome-partitioning/
文章链接https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html
视频讲解https://www.bilibili.com/video/BV1c54y1e7k6

判断回文可以用单独的方法来写并且在单层递归逻辑中调用是回文了加到path里不是就continue
切割线就是startIndex
切割出来的子串用 [startIndex, i] 来表示因为i 总是++的

class Solution {
    List<List<String>> result = new ArrayList<>();
    LinkedList path=new LinkedList<>();

    public List<List<String>> partition(String s) {
        backTracking(s,0);
        return result;
    }
    private 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.removeLast();
        } 
    }
//判断是否是回文子串
    private boolean isPalindrome(String s, int start, int end){
        for (int i = start, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}