代码随想录算法训练营第二十七天|39.组合总和、40.组合总和II、131.分割回文串

39.组合总和

思路：

本题和77.组合，216.组合总和III的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。

本题搜索的过程抽象成树形结构如下：

39.组合总和

注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！

而在77.组合和216.组合总和III中都可以知道要递归K层，因为要取k个元素的组合。

剪枝优化：

在这个树形结构中：

39.组合总和

以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

39.组合总和1

代码：

未剪枝优化

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = [] # 初始化一个空列表，用于存储所有满足条件的组合
        path = [] # 初始化一个空列表，用于存储当前正在构建的组合
        self.backtracking(candidates, target, 0, 0, path, result) # 调用回溯函数开始搜索
        return result # 返回所有满足条件的组合

    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total > target: # 如果当前组合的总和大于目标值，返回上一层
            return
        if total == target: # 如果当前组合的总和等于目标值，则将该组合添加到结果列表中
            result.append(path[:]) # 注意这里使用了切片操作，是为了避免直接添加path的引用，从而确保添加到result中的是组合的一个副本
            return

        for i in range(startIndex, len(candidates)): # 从startIndex开始遍历candidates数组
            total += candidates[i] # 将当前数字添加到当前组合的总和中
            path.append(candidates[i]) # 将当前数字添加到当前正在构建的组合中
            self.backtracking(candidates, target, total, i, path, result) # 递归调用回溯函数，继续搜索。startIndex不用i+1了，表示可以重复使用相同的数
            total -= candidates[i] # 回溯，将当前数字从当前组合的总和中减去
            path.pop() # 回溯，将当前数字从当前正在构建的组合中移除

剪枝优化

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        path = []
        candidates.sort() # 需要排序
        self.backtracking(candidates, target, 0, 0, path, result)
        return result

    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target:
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)):
            if total + candidates[i] > target: # 剪枝操作
                break
            total += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates, target, total, i, path, result)
            total -= candidates[i]
            path.pop()

时间复杂度: O(n * 2^n)，注意这只是复杂度的上界，因为剪枝的存在，真实的时间复杂度远小于此
空间复杂度: O(target)

40. 组合总和 II

思路：

本题的难点在于：集合（数组candidates）有重复元素，但还不能有重复的组合。

一些同学可能想了：我把所有组合求出来，再用set或者map去重，这么做很容易超时！所以要在搜索的过程中就去掉重复组合。

所谓去重，其实就是使用过的元素不能重复选取。

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）强调一下，树层去重的话，需要对数组排序！

选择过程树形结构如图所示：

40.组合总和II

直接用startIndex来去重也是可以的，就不用used数组了

if i > startIndex and candidates[i] == candidates[i - 1]

可以让同一层级，不出现相同的元素（就是重复出现的只保留最左侧的一支树枝，其他的就去重）

代码：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = [] # 初始化结果列表，用于存放所有可能的组合
        path = [] # 初始化当前路径列表，用于构建当前的组合
        candidates.sort() # 对候选数字列表进行排序，以便处理重复数字时能够跳过它们
        self.backtracking(candidates, target, 0, 0, path, result) # 调用回溯方法开始搜索所有可能的组合
        return result # 返回所有有效的组合列表
    
    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target: # 如果当前路径的总和等于目标值，则将当前路径添加到结果列表中
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)): # 遍历候选数字列表，从startIndex开始
            if i > startIndex and candidates[i] == candidates[i - 1]: # 去重。如果当前数字和前一个数字相同，并且不是第一个数字，则跳过，以避免重复的组合
                continue
            if total + candidates[i] > target: # 剪枝。如果加上当前数字后的总和已经超过了目标值，则结束循环
                break
            total += candidates[i] # 将当前数字添加到当前组合的总和中
            path.append(candidates[i]) # 将当前数字添加到当前正在构建的组合中
            self.backtracking(candidates, target, total, i + 1, path, result) # 递归调用回溯函数，继续搜索。更新startIndex为i+1，确保不会重复使用相同的数字
            total -= candidates[i] # 回溯，将当前数字从当前组合的总和中减去
            path.pop() # 回溯，将当前数字从当前正在构建的组合中移除

时间复杂度: O(n * 2^n)
空间复杂度: O(n)

131. 分割回文串

思路：

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

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

这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。

一些同学可能想不清楚回溯究竟是如何切割字符串呢？

我们来分析一下切割，其实切割问题类似组合问题。

例如对于字符串abcdef：

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

所以切割问题，也可以抽象为一棵树形结构，如图：

131.分割回文串

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

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

代码：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = [] # 初始化一个空列表，用于存储所有可能的回文子串组合
        path = [] # 初始化一个空列表，用于在回溯过程中存储当前的回文子串组合
        self.backtracking(s, 0, path, result) # 调用回溯方法开始搜索
        return result # 返回所有可能的回文子串组合
    
    def backtracking(self, s, start_index, path, result ):
        if start_index == len(s): # 如果已经遍历(切割)到字符串的末尾
            result.append(path[:]) # 将当前的回文子串组合添加到结果列表中（注意这里使用了path的副本，避免后续修改影响结果）
            return # 结束递归，返回上一层
        
        for i in range(start_index, len(s)): # 从start_index开始遍历字符串的剩余部分
            if s[start_index: i + 1] == s[start_index: i + 1][::-1]: # 检查从start_index到i的子串是否是回文
                path.append(s[start_index:i+1]) # 如果是回文，则将其添加到当前的回文子串组合中
                self.backtracking(s, i+1, path, result) # 递归调用，从下一个位置继续搜索。注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。
                path.pop() # 回溯，移除最后一个添加的回文子串，尝试其他可能的组合

时间复杂度：O(N * 2 ^ N)，因为总共有O(2^N)种分割方法，每次分割都要判断是否回文需要 O(N) 的时间复杂度。
空间复杂度：O(2 ^ N)，返回结果最多有O(2 ^ N)种划分方法。