代码随想录刷题day27｜组合总和II组合总和II分割回文串

day27学习内容

day27主要内容

• 组合总和
• 组合总和II
• 分割回文串

声明
本文思路和文字，引用自《代码随想录》

一、组合总和-所选数字可重复

39.原题链接

1.1、代码-正确写法

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracking(candidates, target, 0, 0);
        return result;
    }

    private void backTracking(int[] candidates, int target, int sum, int startIndex) {
        // 累加和大于target，直接return
        if (sum > target) {
            return;
        }

        if (sum == target) {
            result.add(new ArrayList(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);
            // 递归
            backTracking(candidates, target, sum + candidates[i], i);
            // 回溯
            path.removeLast();
        }
    }
}

1.1.1、为什么递归取的是i而不是i+1呢？

看题意，
题目中说的很清楚了，可以无限制重复选取，所以不是从n+1开始迭代的。

二、组合总和II-所选数字不可重复

40.原题链接

2.1、和39题有什么不同

不同点1：看题目，原始数组中有重复的元素。

不同点2：累加求和的时候，可以用同样的元素。但是很重要的一点是每个数字在每个组合中只能使用一次。

2.2、思路

• 对树层进行去重，对树枝不去重

2.2.1、初始化

• LinkedList<Integer> path：用于临时存储当前探索路径中的数字序列。
• List<List<Integer>> ans：用来存储所有符合条件的组合。
• boolean[] used：标记数组中的元素是否被使用过，以避免在同一层中重复使用相同的元素。
• int sum：记录当前路径上所有元素的总和。

2.2.2、主要步骤

1. 排序：首先对数组 candidates 进行排序，这是为了实现有效去重和提前终止搜索。
2. 调用回溯函数：通过 backTracking 函数开始回溯搜索。

2.2.3、回溯函数 backTracking

• 结束条件：当 sum（当前路径元素的总和）等于 target 时，将当前路径复制一份并添加到结果集 ans 中，然后返回上一层继续探索。
• 遍历候选数组：从 startIndex 开始遍历 candidates 数组，以避免重复使用元素。
• 剪枝条件：
  • 如果当前元素加上 sum 超过了 target，则由于数组已经排序，后面的元素只会更大，所以直接中断当前循环。
  • 如果当前元素与前一个元素相同，且前一个元素未被使用过，则跳过当前元素。这一步是去重的关键。
• 递归与回溯：
  • 首先标记当前元素为已使用，将其加入 path，并更新 sum。
  • 然后递归调用 backTracking，注意 startIndex 更新为 i + 1，因为每个元素只能使用一次。
  • 递归返回后，撤销当前元素的选择：将其标记为未使用，从 path 中移除，并更新 sum。

通过这样的递归+回溯的方式，加上有效的剪枝条件，代码能够高效地搜索整个解空间，找出所有满足条件的组合。排序是去重和剪枝的基础，确保了算法的高效和正确性。

2.3、正确写法1

class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] used;
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        // 加标志，用来判断同层节点是否已经遍历
        Arrays.fill(used, false);
        // 去重必须先排序
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return ans;
    }

    private void backTracking(int[] candidates, int target, int startIndex) {
        if (sum == target) {
            ans.add(new ArrayList(path));
        }
        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]) {
                continue;
            }
            used[i] = true;
            sum += candidates[i];
            path.add(candidates[i]);
            // 每个节点仅能选择一次，所以从下一位开始
            backTracking(candidates, target, i + 1);
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

2.3.1、为什么要先排序

• 去重逻辑的实现：
  • 排序是实现去重逻辑的前提。当数组被排序后，重复的数字会被排列在一起。
  • 在回溯过程中，为了避免选择相同的数字造成的重复组合，需要检查当前数字是否与前一个数字相同，如果相同且前一个数字没有被使用（即在这一层中还未使用过），则跳过当前数字。
  • 如果数组未排序，重复的数字可能散布在数组中的不同位置，我们就不能通过比较当前数字和前一个数字是否相同来有效地去重。
• 提前终止搜索：
  • 排序还允许我们在确定总和已经超过目标值时提前终止搜索。因为数组是有序的，
  • 如果在某一点上，当前路径上的数字总和加上当前考虑的数字已经超过了目标值，那么对于当前数字之后的所有数字，它们加入路径的结果也都会超过目标值（因为它们都是非负的，并且等于或大于当前数字）。
  • 这样可以避免无谓的搜索，从而提高算法的效率。

2.3.2、去重为什么是!used[i - 1]而不是used[i - 1]

看卡尔大佬的图，或者自己画个图，就很好理解了。简单来说，就是当你递归到最后一层往回回溯时，之前的节点，used的状态会重新变回[0]

三、分割回文串

131.原题链接

3.1、科普-什么是回文串？

来自gpt的解释：回文是一种特殊的字符串，它从前往后读和从后往前读是完全相同的。回文不仅限于单词和短语，也可以是一系列数字、字符或者其他序列，它们的特点是对称性。这种对称可以是字符级的，也就是说，忽略空格、标点符号和大小写后，字符串的前半部分和后半部分是镜像对称的。

3.2、思路

• 什么时候分割结束
  • 看卡尔画出来的树图或者自己画一个，很明显到了字符串的末尾(可以理解为是叶子结点)，就说明分割结束了。
• 那么什么时候可以返回结果
  • 很明显，是回文字符串的时候，才能放入结果集。
• 综上所述，这道问题就变成了判断每一个叶子结点是不是回文子串。如果叶子结点是回文字符串，就直接返回即可。
• 怎么切割字符串
  • S0tring.subString()这方法应该知道吧。问题在于从哪里切割到哪里，
  • 答案是从startIndex切割到i。而且是左闭右闭。为什么呢？看3.3.2。

3.3、代码-正确写法

class Solution {
    List<List<String>> result= new ArrayList<>();
    Deque<String> deque = 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()) {
        	//为什么看到结果就add了呢？请看3.3.1
            result.add(new ArrayList(deque));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            // 判断是不是回文串，如果是就加入到deque里面
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                deque.addLast(str);
            } else {
                continue;
            }
            // 起始位置+1，不能取已经取过的字符串。
            backTracking(s, i + 1);
            deque.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;
    }
}

3.3.1、为什么看到deque结果就往最终的result里面add？

因为判断回文子串，是在单层逻辑里面判断的，在deque里面的字符串，一定是回文子串，不是回文子串不会往里面add的。所以可以无脑add。

3.3.2、为什么判断回文串是从i开始，截取却从i+1开始呢？

• 在这段代码中，判断回文串是从startIndex到i（包括i），这是因为需要检查从startIndex到i的子字符串是否构成回文串。
• 一旦确认这个子字符串是回文串，就加入deque中。
• 截取从i+1开始是因为在回溯过程中，当我们确定了一个回文子字符串后，下一步应该从这个子字符串的下一个字符开始继续寻找新的回文子字符串。这样，我们可以确保不会重复使用已经被包含在找到的回文子字符串中的字符。
• 例如，对于字符串"aab"，当startIndex为0，且我们发现"aa"是回文时，下一次递归调用backTracking时的startIndex应该是2，即"aa"之后的字符，这就是为什么截取开始的索引是i+1。这样做可以避免重复处理相同的字符，确保每次递归都是针对剩余未处理的字符串部分。

总结

1.感想

• 分割回文串这题好难，不咋会写，另外吐槽一下，卡尔老师的视频反光好严重。

2.思维导图

本文思路引用自代码随想录，感谢代码随想录作者。