- 组合总和
本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制
题目链接/文章讲解：https://programmercarl.com/0039.组合总和.html
视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
思考
这道题的特点是可以重复选取。
因此for循环内遍历的时候，start_index = i
class Solution:def __init__(self):self.path = []self.res_list_all = []self.sum = 0def backtracking(self,candidates,target,start_index):if self.sum == target:self.res_list_all.append(self.path[:])return elif self.sum > target:return else:for i in range(start_index,len(candidates)):self.path.append(candidates[i])self.sum+=candidates[i]self.backtracking(candidates,target,i)self.path.pop()self.sum-=candidates[i]def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:self.backtracking(candidates,target,0)return self.res_list_all
排序后，回溯的过程可以剪枝，同一层，前面的数和已经超了的话，后面的就不用再试了，因为后面的数更大。
class Solution:def __init__(self):self.path = []self.res_list_all = []self.sum = 0def backtracking(self,candidates,target,start_index):if self.sum == target:self.res_list_all.append(self.path[:])return elif self.sum > target:return else:for i in range(start_index,len(candidates)):if self.sum+candidates[i] > target:breakself.path.append(candidates[i])self.sum+=candidates[i]self.backtracking(candidates,target,i)self.path.pop()self.sum-=candidates[i]def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.backtracking(candidates,target,0)return self.res_list_all
40.组合总和II
本题开始涉及到一个问题了：去重。
注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。
题目链接/文章讲解：https://programmercarl.com/0040.组合总和II.html
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
思考
这道题的难点是要在回溯中去重，即去除重复的组合。
两种方法:
- 需要定义一个used数组。
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过
2. 判断条件增加i>start_index
两种方案都需要先排序才能去重。
方案二的方法
class Solution:def __init__(self):self.res = []self.res_all = []self.sum = 0def backtracking(self,candidates,target,start_index):if self.sum > target:returnif self.sum == target:self.res_all.append(self.res[:])returnfor i in range(start_index,len(candidates)):if i > start_index and (candidates[i-1] == candidates[i]):continueself.sum+=candidates[i]self.res.append(candidates[i])self.backtracking(candidates,target,i+1)self.res.pop()self.sum-=candidates[i]def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.backtracking(candidates,target,0)return self.res_all
131.分割回文串
本题较难，大家先看视频来理解 分割问题，明天还会有一道分割问题，先打打基础。
https://programmercarl.com/0131.分割回文串.html
视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
思考
分割问题本质上也是求组合问题。start_index表示分割线。
def is_huiwen(s):i = 0j = len(s)-1while i<j:if s[i]==s[j]:i+=1j-=1else:return Falsereturn True
class Solution:def partition(self, s: str) -> List[List[str]]:def backtracking(s,star_index):if star_index == len(s):res.append(path[:])returnfor i in range(star_index,len(s)):if is_huiwen(s[star_index:i+1]):path.append(s[star_index:i+1])backtracking(s,i+1)path.pop()path = []res = []backtracking(s,0)return res
