- 组合总和
本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 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 = 0
def 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 = 0
def 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:
break
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]]:
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 = 0
def backtracking(self,candidates,target,start_index):
if self.sum > target:
return
if self.sum == target:
self.res_all.append(self.res[:])
return
for i in range(start_index,len(candidates)):
if i > start_index and (candidates[i-1] == candidates[i]):
continue
self.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 = 0
j = len(s)-1
while i<j:
if s[i]==s[j]:
i+=1
j-=1
else:
return False
return True
class Solution:
def partition(self, s: str) -> List[List[str]]:
def backtracking(s,star_index):
if star_index == len(s):
res.append(path[:])
return
for 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