目录
详细布置：
1. 39. 组合总和
2. 40. 组合总和 II
3. 131. 分割回文串
详细布置：
1. 39. 组合总和
给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为
target的不同组合数少于150个。
建议：本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制
本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。
本题搜索的过程抽象成树形结构如下：
class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total > target:returnif total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):total += candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i, path, result) # 不用i+1了，表示可以重复读取当前的数total -= candidates[i]path.pop()def combinationSum(self, candidates, target):result = []self.backtracking(candidates, target, 0, 0, [], result)return result2. 40. 组合总和 II
给定一个候选人编号的集合
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用 一次 。注意：解集不能包含重复的组合。
建议：本题开始涉及到一个问题了：去重。
注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
所以要在搜索的过程中就去掉重复组合。
所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）
强调一下，树层去重的话，需要对数组排序！
class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if i > startIndex and candidates[i] == candidates[i - 1]:continueif total + candidates[i] > target:breaktotal += candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i + 1, path, result)total -= candidates[i]path.pop()def combinationSum2(self, candidates, target):result = []candidates.sort()self.backtracking(candidates, target, 0, 0, [], result)return result3. 131. 分割回文串
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是回文串 。返回
s所有可能的分割方案。
本题这涉及到两个关键问题：
- 切割问题，有不同的切割方式
- 判断回文
相信这里不同的切割方式可以搞懵很多同学了。
这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。
一些同学可能想不清楚 回溯究竟是如何切割字符串呢？
我们来分析一下切割，其实切割问题类似组合问题。
class Solution:def partition(self, s: str) -> List[List[str]]:'''递归用于纵向遍历for循环用于横向遍历当切割线迭代至字符串末尾，说明找到一种方法类似组合问题，为了不重复切割同一位置，需要start_index来做标记下一轮递归的起始位置(切割线)'''result = []self.backtracking(s, 0, [], result)return resultdef backtracking(self, s, start_index, path, result ):# Base Caseif start_index == len(s):result.append(path[:])return# 单层递归逻辑for i in range(start_index, len(s)):# 此次比其他组合题目多了一步判断：# 判断被截取的这一段子串([start_index, i])是否为回文串if self.is_palindrome(s, start_index, i):path.append(s[start_index:i+1])self.backtracking(s, i+1, path, result) # 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串path.pop() # 回溯def is_palindrome(self, s: str, start: int, end: int) -> bool:i: int = start j: int = endwhile i < j:if s[i] != s[j]:return Falsei += 1j -= 1return True 
