本题是?集合里元素可以用无数次，那么和组合问题的差别?其实仅在于?startIndex上的控制
class Solution:
def combinationSum(self, candidates, target):
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:
continue
total += candidates[i]
path.append(candidates[i])
self.backtracking(candidates, target, total, i, path, result)
total -= candidates[i]
path.pop()本题开始涉及到一个问题了：去重：①树层去重②树枝去重
注意题目中给我们?集合是有重复元素的，那么求出来的?组合有可能重复，但题目要求不能有重复组合。?
注意判断是树层还是树枝
class Solution:
def backtracking(self, candidates, target, total, startIndex, used, path, result):
if total == target:
result.append(path[:])
return
?#剪枝操作（树层去重）在单层逻辑里面
for i in range(startIndex, len(candidates)):
# 对于相同的数字，只选择第一个未被使用的数字，跳过其他相同数字
if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]:
continue
if total + candidates[i] > target:
break
total += candidates[i]
path.append(candidates[i])
used[i] = True
self.backtracking(candidates, target, total, i + 1, used, path, result)
used[i] = False
total -= candidates[i]
path.pop()
def combinationSum2(self, candidates, target):
used = [False] * len(candidates)
result = []
candidates.sort()
self.backtracking(candidates, target, 0, 0, used, [], result)
return result
本题较难，大家先看视频来理解?分割问题
判断回文子串为什么放在单层逻辑里，而不是放在终止条件里
如何表示切割的范围
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 ):
# Base Case
if start_index == len(s):
result.append(path[:])
return
# 单层递归逻辑
for i in range(start_index, len(s)):
# 若反序和正序相同，意味着这是回文串
if s[start_index: i + 1] == s[start_index: i + 1][::-1]:
path.append(s[start_index:i+1])
# 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串
self.backtracking(s, i+1, path, result)
path.pop() # 回溯?