39. 组合总和
思路
根据题意画二叉树
这道题与之前的组合总和的区别在于，数组中的数字可以多次使用，因此每次递归时的startIndex依旧是从当前的i开始
尝试写代码：
class Solution:
def __init__(self):
self.path = []
self.result = []
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.backtracking(candidates, target, 0, 0)
return self.result
def backtracking(self, candidates, target, startIndex, sum):
if sum == target:
self.result.append(self.path[:])
return
if sum > target:
return
for i in range(startIndex, len(candidates)):
sum += candidates[i]
self.path.append(candidates[i])
self.backtracking(candidates, target, i, sum)
sum -= candidates[i]
self.path.pop()
成功通过
根据代码随想录
可以剪枝，先对数组排序，然后在for循环中一开始，先判断当前sum + 当前值是否大于目标值，如果是，就continue
最终代码：
class Solution:
def __init__(self):
self.path = []
self.result = []
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
self.backtracking(candidates, target, 0, 0)
return self.result
def backtracking(self, candidates, target, startIndex, sum):
if sum == target:
self.result.append(self.path[:])
return
for i in range(startIndex, len(candidates)):
if sum + candidates[i] > target:
continue
sum += candidates[i]
self.path.append(candidates[i])
self.backtracking(candidates, target, i, sum)
sum -= candidates[i]
self.path.pop()
40. 组合总和 II
思路
由于给定的数组中包含重复元素，最终结果可能出现重复的组合，因此需要对最终结果进行去重
在python中，每次得到的组合加入result之前，先判断下result中是否有该组合
尝试写代码：
class Solution:
def __init__(self):
self.path = []
self.result = []
def backtracking(self, candidates, target, startIndex, sum):
if sum == target:
if self.path not in self.result:
self.result.append(self.path[:])
return
if sum > target:
return
for i in range(startIndex, len(candidates)):
sum += candidates[i]
self.path.append(candidates[i])
self.backtracking(candidates, target, i + 1, sum)
sum -= candidates[i]
self.path.pop()
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
self.backtracking(candidates, target, 0, 0)
return self.result
结果不对，去重失败，因为每个组合的排列顺序不一样，无法通过简单的in来判断。
换一种思路，先排序，如果i + 1 == i，在这里进行去重
尝试写代码
class Solution:
def __init__(self):
self.path = []
self.result = []
def backtracking(self, candidates, target, startIndex, sum):
if sum == target:
if self.path not in self.result:
self.result.append(self.path[:])
return
for i in range(startIndex, len(candidates)):
if sum + candidates[i] > target:
continue
if i - 1 and i - 1 == i:
continue
sum += candidates[i]
self.path.append(candidates[i])
self.backtracking(candidates, target, i + 1, sum)
sum -= candidates[i]
self.path.pop()
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
self.backtracking(candidates, target, 0, 0)
return self.result
测试用例通过，但总体超出时间限制
根据代码随想录
注意：
- 剪枝，在for循环内先判断，如果sum与当前值的和大于目标值，break
- 去重，如果当前值与上一个值相等，continue
- 去重时有两种方法，一是i > startIndex；一是使用used
最终代码，使用i > startIndex
class Solution:
def __init__(self):
self.path = []
self.result = []
def backtracking(self, candidates, target, startIndex, sum):
if sum == target:
self.result.append(self.path[:])
return
for i in range(startIndex, len(candidates)):
if i > startIndex and candidates[i - 1] == candidates[i]:
continue
if sum + candidates[i] > target:
break
sum += candidates[i]
self.path.append(candidates[i])
self.backtracking(candidates, target, i + 1, sum)
sum -= candidates[i]
self.path.pop()
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
self.backtracking(candidates, target, 0, 0)
return self.result
使用used
class Solution:
def __init__(self):
self.path = []
self.result = []
def backtracking(self, candidates, target, startIndex, sum, used):
if sum == target:
self.result.append(self.path[:])
return
for i in range(startIndex, len(candidates)):
if i > 0 and candidates[i - 1] == candidates[i] and not used[i - 1]:
continue
if sum + candidates[i] > target:
break
sum += candidates[i]
self.path.append(candidates[i])
used[i] = True
self.backtracking(candidates, target, i + 1, sum, used)
sum -= candidates[i]
self.path.pop()
used[i] = False
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
used = [False] * len(candidates)
candidates.sort()
self.backtracking(candidates, target, 0, 0, used)
return self.result
总结
整体思路正确，但是具体写代码的去重逻辑时，有错误
131. 分割回文串
思路
画出树形结构图
不知道分割在递归代码中怎么写
根据代码随想录
分割问题和组合问题非常像
要点：
- 切割线可以用startIndex表示，即终止条件是当startIndex == len(s)
- 判断回文的逻辑放在单层递归中
- 如何表示切割的子串：可以用
[startIndex, i]表示切割的子串
最终代码：
class Solution:
def __init__(self):
self.path = []
self.result = []
def isHui(self, string, start, end):
while start < end:
if string[start] != string[end]:
return False
start += 1
end -= 1
return True
def partition(self, s: str) -> List[List[str]]:
self.backtracking(s, 0)
return self.result
def backtracking(self, s, startIndex):
if startIndex == len(s):
self.result.append(self.path[:])
return
for i in range(startIndex, len(s)):
if self.isHui(s, startIndex, i):
self.path.append(s[startIndex:i + 1])
else:
continue
self.backtracking(s, i + 1)
self.path.pop()
