算法打卡day23
今日任务：
1）39. 组合总和
2）40.组合总和II
3）131.分割回文串
39. 组合总和
题目链接：39. 组合总和 - 力扣（LeetCode）
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为： [ [7], [2,2,3] ]示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
文章讲解：代码随想录 (programmercarl.com)
视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！哔哩哔哩bilibili
思路：
定义一个回溯函数
backtrack，它接受两个参数：start表示从候选数字列表中的哪个位置开始搜索，div表示目标值与当前路径数字之差。在回溯函数中，首先判断终止条件：
- 如果
div等于 0，说明当前路径上的数字组合的和等于目标值，将当前组合添加到结果列表中并返回。- 如果
div小于 0，说明当前路径上的数字组合的和已经超过目标值，不再继续搜索，直接返回。然后，使用一个循环遍历候选数字列表中的数字，从
start位置开始：
- 将当前数字添加到当前路径中。
- 递归调用
backtrack函数，传入更新后的start位置和更新后的div值（减去当前数字）。- 递归调用结束后，回溯，将当前数字从当前路径中移除。
最终，当所有可能的组合都搜索完毕后，返回结果列表。
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.candidates = candidatesself.path = []self.result = []self.backtrack(0, target)return self.resultdef backtrack(self, start, div):# 终止条件if div == 0: # 如果目标值为 0，将当前组合添加到结果列表中并返回self.result.append(self.path[:])returnelif div < 0: # 如果目标值为负数，直接返回，不再继续搜索returnfor i in range(start, len(self.candidates)):self.path.append(self.candidates[i])self.backtrack(i, div - self.candidates[i])self.path.pop()改进：
我们可以先对列表排序，对于有序列表，剪枝效果更好
我们还可以直接传递path变量，而不是作为成员变量，在传递的过程可以采用隐式回溯
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.candidates = candidatesself.result = []self.backtrack(0, target, [])return self.resultdef backtrack(self, start, div, path):# 终止条件:目标值为 0，将当前组合添加到结果列表中并返回if div == 0:self.result.append(path[:])return# 递归层for i in range(start, len(self.candidates)):# 提前剪枝：如果当前候选数大于目标值，直接跳过if self.candidates[i] > div:break# 递归调用self.backtrack(i, div - self.candidates[i], path + [self.candidates[i]])40.组合总和II
题目链接：40. 组合总和 II - 力扣（LeetCode）
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[ [1,1,6],
[1,2,5],
[1,7],
[2,6] ]示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[ [1,2,2],
[5] ]提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
文章讲解：代码随想录 (programmercarl.com)
视频讲解：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II哔哩哔哩bilibili
思路：
已经做了上一题，这一题比较简单了，先排序，遍历列表，如果遇到重复的跳过
class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.candidates = candidatesself.result = []self.backtrack(0, target, [])return self.resultdef backtrack(self, start, div, path):# 终止条件if div == 0:self.result.append(path[:])returnfor i in range(start, len(self.candidates)):# 提前剪枝：如果当前候选数大于目标值，直接跳过if div < self.candidates[i]:break# 避免重复：如果当前候选数和前一个候选数相同，跳过本次循环if i > start and self.candidates[i] == self.candidates[i - 1]:continueself.backtrack(i + 1, div - self.candidates[i], path + [self.candidates[i]])131.分割回文串
题目链接：131. 分割回文串 - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)
视频讲解：带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！哔哩哔哩bilibili
思路：
这一题难一点
- 我们可以使用回溯算法来生成所有可能的分割方案。
- 在每一步中，我们可以从当前位置开始向右扩展，检查以当前位置开头的所有子串是否为回文串。
- 如果是回文串，我们将该子串添加到当前路径中，并递归地处理剩余部分。
- 当处理到字符串末尾时，将当前路径添加到结果中。
class Solution:def partition(self, s: str) -> List[List[str]]:self.s = sself.result = []self.backtrack(0, len(self.s), [])return self.resultdef backtrack(self, start, stop, path):# 终止条件：if start == len(self.s):self.result.append(path[:])return# 从当前位置开始向右扩展，检查以当前位置开头的所有子串是否为回文串for i in range(start,len(self.s)):# 判断以i为切分点，判断i之前（包含i）的字符串是否为回文串substring = self.s[start:i+1]if substring == substring[::-1]:path.append(substring)self.backtrack(i+1,len(self.s),path)path.pop()
感想：这一题后面还要再看看，不是很熟练