代码随想录算法训练营第27天(回溯算法03 |● 39. 组合总和 ● 40.组合总和II ● 131.分割回文串

发布时间:2024年01月22日

39. 组合总和

本题是 集合里元素可以用无数次,那么和组合问题的差别 其实仅在于 startIndex上的控制
题目链接: 39. 组合总和
文章讲解: 39. 组合总和
视频讲解: 39. 组合总和

解题思路

本题没有组合数量要求,仅仅是总和的限制,所以递归没有层数的限制,只要选取的元素总和超过target,就返回!
而在77.组合 216.组合总和III中都可以知道要递归K层,因为要取k个元素的组合。

回溯三部曲

  1. 递归函数参数:
    二维数组result存放结果集
    数组path存放符合条件的结果
    int型的sum变量来统计单一结果path里的总和
    startIndex来控制for循环的起始位置
  2. 递归终止条件:
    sum大于target和sum等于target
  3. 单层搜索逻辑:
    单层for循环依然是从startIndex开始,搜索candidates集合。

剪枝操作

对于sum已经大于target的情况,其实是依然进入了下一层递归,只是下一层递归结束判断的时候,会判断sum > target的话就返回。其实如果已经知道下一层的sum会大于target,就没有必要进入下一层递归了。那么可以在for循环的搜索范围上进行剪枝。
对总集合排序之后,如果下一层的sum(就是本层的 sum + candidates[i])已经大于target,就可以结束本轮for循环的遍历。

  1. Arrays.sort(candidates); // 先进行排序
  2. for(int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++)//剪枝

总结

本题和我们之前讲过的77.组合216.组合总和III 有两点不同:

  1. 组合没有数量要求
  2. 元素可无限重复选取
// 回溯 已剪枝
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    int sum = 0;
    int startIndex = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // 先进行排序
        backtracking(candidates, target, sum, startIndex);
        return result;
    }
    public 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 && sum + candidates[i] <= target; i++){  //剪枝  控制树的横向遍历
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, target, sum, i); // 控制树的纵向遍历
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

40.组合总和II

本题开始涉及到一个问题了:去重。
注意题目中给我们 集合是有重复元素的,那么求出来的 组合有可能重复,但题目要求不能有重复组合。
题目链接: 40.组合总和II
文章讲解:[ 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)

解题思路

这道题目和39.组合总和如下区别:

  1. 本题candidates 中的每个数字在每个组合中只能使用一次。
  2. 本题数组candidates的元素是有重复的,而39.组合总和是无重复元素的数组candidates

我们要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重。我们要做的是数层方面的去重,used[]数组进行去重.树层去重的话,需要先对数组排序!

去重逻辑

  1. 当前数字是否与前一个数字相同
  2. 前一个数是否已经被使用过了

回溯三部曲

  1. 递归函数参数:
    二维数组result存放结果集
    数组path存放符合条件的结果
    int型的sum变量来统计单一结果path里的总和
    startIndex来控制for循环的起始位置
    bool型数组used,用来记录同一树枝上的元素是否使用过。
  2. 递归终止条件:
    sum大于target和sum等于target
  3. 单层递归逻辑:
    去重逻辑:
    如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false,就说明:前一个树枝,使用了candidates[i - 1],也就是说同一树层使用过candidates[i - 1]。
    此时for循环里就应该做continue的操作。
    used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
    used[i - 1] == false,说明同一树层candidates[i - 1]使用过
// 回溯  已剪枝
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    int sum = 0;
    int startIndex = 0;
    boolean used[];
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.sort(candidates); // 先进行排序
        backtracking(candidates, target, sum, startIndex, used);
        return result;
    }
    public void backtracking(int[] candidates, int target, int sum, int startIndex, boolean[] used){
        if(sum > target) return;
        if(sum == target){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++){  //剪枝  控制树的横向遍历
            if(i >0 && candidates[i-1] == candidates[i] && used[i-1] == false) continue; // 去重
            used[i] = true;
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, target, sum, i+1, used); // 控制树的纵向遍历
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

131.分割回文串 (需复习

本题较难,大家先看视频来理解 分割问题,明天还会有一道分割问题,先打打基础。
题目链接: 131.分割回文串
文章讲解: 131.分割回文串
视频讲解: 131.分割回文串

解题思路

回溯三部曲

  1. 递归函数参数:
    全局变量数组path存放切割后回文的子串
    二维数组result存放结果集
    startIndex,因为切割过的地方,不能重复切割,和组合问题也是保持一致的。
  2. 终止条件:
    切割线切到了字符串最后面,说明找到了一种切割方法。startIndex就是切割线。
  3. 单层搜索逻辑:
    在for (int i = startIndex; i < s.size(); i++)循环中,我们 定义了起始位置startIndex,那么 [startIndex, i] 就是要截取的子串。首先判断这个子串是不是回文,如果是回文,就加入在vector path中,path用来记录切割过的回文子串。

如何更高效的计算一个子字符串是否是回文字串呢,我们这里是用双指针实现的,可以用动态规划来优化。后续学了动态规划再说吧

本题难点

列出如下几个难点:

  • 切割问题可以抽象为组合问题
  • 如何模拟那些切割线
  • 切割问题中递归如何终止
  • 在递归循环中如何截取子串
  • 如何判断回文
// 回溯
class Solution {
    List<List<String>> result = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return result;
    }

    private void backTracking(String s, int startIndex) {
        //如果起始位置大于s的大小,说明找到了一组分割方案
        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 startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}
文章来源:https://blog.csdn.net/weixin_46743838/article/details/135746789
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。