算法训练营第二十天 | 回溯算法（二）

一、Leetcode 39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

示例：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

引用：

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

和 Leetcode 216.组合总和Ⅲ 不同之处在于，这次的组合可以含有重复数字。

所以不同点在于，我们进行递归调用的时候，传递的起始位置是 i 而不是 i+1。

这意味着，以当前这个数字为起始位置开始遍历，下次遍历的时候，还是以这个数字为起始位置，这样就包含了重复元素。

其他细节和之前差不多，不多说。

代码：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.result = []
        self.path = []
        self.cur_sum = 0
        self.backtracking(candidates, target, 0)
        return self.result

    def backtracking(self, candidates, target, startindex):
        if self.cur_sum == target:
            self.result.append(self.path[:])
            return
        if self.cur_sum > target:
            return

        for i in range(startindex, len(candidates)):
            self.path.append(candidates[i])
            self.cur_sum += candidates[i]
            self.backtracking(candidates, target, i)
            self.path.pop()
            self.cur_sum -= candidates[i]
        

二、Leetcode 40.组合总和Ⅱ

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates中的每个数字在每个组合中只能使用 一次 。

**注意：解集不能包含重复的组合。 **

示例：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

引用：

原文链接：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
题目链接：https://leetcode.cn/problems/combination-sum-ii/description/
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A/

本题的重点在于，每个数字只能使用一次，所以就需要一个去重操作。
在调用递归之前，对 candidates 进行一次排序，这样可以方便我们进行去重。

去重逻辑：

• i > startindex：这个条件用于保证当前处理的元素并非当前递归层的首个元素。在回溯算法中，startindex代表当前递归层能够选取元素的起始位置。当i等于startindex时，说明当前元素是该层递归里第一个被考虑的元素，无论它是否和前一个元素相同，都要进行处理。
• candidates[i] == candidates[i - 1]：此条件用于检查当前元素是否和前一个元素相同。若相同，就意味着可能会产生重复的组合。
• continue：当上述两个条件都满足时，跳过当前元素，直接处理下一个元素，以此避免产生重复的组合。

代码：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        self.result = []
        self.path = []
        self.cur_sum = 0
        # 对候选数组进行排序，方便后续去重
        candidates.sort()
        self.backtracking(candidates, target, 0)
        return self.result

    def backtracking(self, candidates, target, startindex):
        if self.cur_sum == target:
            self.result.append(self.path[:])
            return
        if self.cur_sum > target:
            return

        for i in range(startindex, len(candidates)):
            # 去重逻辑
            if i > startindex and candidates[i] == candidates[i - 1]:
                continue
            self.path.append(candidates[i])
            self.cur_sum += candidates[i]
            self.backtracking(candidates, target, i + 1)
            self.path.pop()
            self.cur_sum -= candidates[i]
    

组合总和问题总结：

• 组合总和（39 题）：因为同一个数字可以无限制重复被选取，所以在递归调用时，传递的索引是当前索引i，即下一次还可以选择当前数字。
• 组合总和 II（40 题）：由于每个数字在每个组合中只能使用一次，并且要处理元素重复的情况，所以在递归调用时，传递的索引是i + 1，同时需要进行去重操作，以避免在同一树层上选择相同的元素造成重复组合。
• 组合总和 III（216 题）：限制了只能使用 1 到 9 的数字，且每个数字最多使用一次，在递归时需要控制数字的范围和使用次数，从 1 开始到 9 结束，每次递归传递i + 1作为下一次搜索的起始索引，同时记录当前组合中数字的个数和总和，当数字个数达到k且总和等于n时，将当前组合加入结果集。

三、Leetcode 131.分割字符串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

引用：

原文链接：https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
题目链接：https://leetcode.cn/problems/palindrome-partitioning/description/
视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6/

本题这涉及到两个关键问题：

• 切割问题，有不同的切割方式
• 判断回文

判断回文的话，我们在双指针算法中已经接触过了，这里就简单定义了一个判断回文的函数，不再详细解释。

关于切割问题，其实很像一个组合问题。

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…。
• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

递归三部曲：

函数的主要参数和返回值：

1. 无返回值
2. 和组合问题一样，参数依然是 startindex 和题目要求的字符串。

函数的终止条件：
当 startindex 大于字符串的长度的时候，说明整个字符串已经遍历完成，此时进行递归返回并保存结果。

单层递归的逻辑：
在字符串中将我们进行遍历的子串取出，并进行回文判断。当它是回文时，我们进行递归和回溯操作。

代码：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.result = []
        self.path = []
        self.backtracking(s, 0)
        return self.result


    def backtracking(self, s, startindex):
        if startindex >= len(s):
            self.result.append(self.path[:])
            return 

        for i in range(startindex, len(s)):
            cur_s = s[startindex:i+1]
            if self.is_palindrome(cur_s):
                self.path.append(cur_s)
                self.backtracking(s, i+1)
                self.path.pop()



    def is_palindrome(self, s):
        i = 0
        j = len(s)-1
        while i <= j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True