39. 组合总和
- 思路
- example
- 回溯：深度由sum_ vs target控制，宽度由startIndex控制。
- candidates中无重复元素
- 不需要考虑同层去重
- 无限制重复被选取 （有放回）
- startIndex取当前位置
- "去重“：排序 + startIndex
无重可复选
注意：本题不需预先排序。
- 剪枝
- 模向 （for 循环内）
- 纵向 （递归函数base case)
- 2 <= candidates[i] <= 40
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(candidates, start, sum_):
if sum_ == target:
res.append(path[:])
return
for i in range(start, len(candidates)):
if sum_ + candidates[i] > target:
break
path.append(candidates[i])
sum_ += candidates[i]
backtrack(candidates, i, sum_)
sum_ -= candidates[i]
path.pop()
candidates.sort()
res, path = [], []
backtrack(candidates, 0, 0)
return res
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(candidates, start, sum_):
if sum_ > target:
return
if sum_ == target:
res.append(path[:])
return
for i in range(start, len(candidates)):
# 在这里提早剪枝更好一些
path.append(candidates[i])
sum_ += candidates[i]
backtrack(candidates, i, sum_)
sum_ -= candidates[i]
path.pop()
res, path = [], []
backtrack(candidates, 0, 0)
return res
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start):
if path and sum(path) == target:
res.append(path[:])
return
if path and sum(path) > target:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i) # !!! 可重复取
path.pop()
res, path = [], []
backtrack(0)
return res
- 另一种写法
- 深度：逐个遍历candidates
- 宽度：每个candidate选取可能性：0，1，2，。。。
TBA
40. 组合总和 II
- 思路
- example
- candidates有重复元素
- 同层去重
if i > start and candidates[i] == candidates[i-1]:
continue
- candidates 中的每个数字在每个组合中只能使用 一次
- 复杂度. 时间：O(?), 空间: O(?)
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(candidates, start, sum_):
if sum_ == target:
res.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]:
continue
if sum_ + candidates[i] > target:
break
path.append(candidates[i])
sum_ += candidates[i]
backtrack(candidates, i+1, sum_)
sum_ -= candidates[i]
path.pop()
res, path = [], []
candidates.sort()
backtrack(candidates, 0, 0)
return res
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(candidates, start, sum_): # sum_ 还没有计入start位置的贡献
if sum_ > target: # 剪枝
return
if sum_ == target: # 终止条件
res.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]: # 去重
continue
# 也可以在这里剪枝
path.append(candidates[i])
sum_ += candidates[i]
backtrack(candidates, i+1, sum_) # 无放回情况
sum_ -= candidates[i]
path.pop()
candidates.sort() # candidates中有重复
res, path = [], []
backtrack(candidates, 0, 0)
return res
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start):
if path and sum(path) > target:
return
if path and sum(path) == target:
res.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]: # !!!
continue
path.append(candidates[i])
backtrack(i+1)
path.pop()
candidates.sort() # !!!
res, path = [], []
backtrack(0)
return res
-
参考 (使用used数组）
image - 复习 216. 组合总和 III
- 无重不可复选
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtrack(start, sum_):
if sum_ > n:
return
if len(path) == k:
if sum_ == n:
res.append(path[:])
return
for i in range(start, 9-(k-len(path))+2):
path.append(i)
sum_ += i
backtrack(i+1, sum_)
sum_ -= i
path.pop()
res, path = [], []
backtrack(1, 0)
return res
-
小结：组合
- 去重 （sort, startIndex)
- 剪枝
- 个数
- target, sum_, ...
- 有放回 vs 无放回
- startIndex: i vs i + 1
-
桶装球 vs 球装桶
- 桶的限制？球的限制？
- 桶装球：桶视角。深度=桶，宽度=球（可选范围，规格，限制，每次选一个球）
- 球装桶：球视角。深度=球，宽度=桶（桶的体积，规格，限制，可能取多个球）
131. 分割回文串
- 思路
- example
- 返回 s 所有可能的分割方案: 暴力回溯。
- 切割 （转化为组合问题）
-
判断回文 （双指针）
- 暴力回溯：
- 桶装球
- 深度：切割位置 （子串起始位置startIndex），桶
- 宽度：切割位置 （子串结束位置），球
- 复杂度. 时间：
, 空间:
- worst case: s = ‘aaaaaaaaa’
class Solution:
def partition(self, s: str) -> List[List[str]]:
def isPalindrome(s, left, right): # [left, right]
while left < right:
if s[left] == s[right]:
left += 1
right -= 1
else:
return False
return True
def backtrack(s, start):
if start == len(s):
res.append(path[:])
return
for i in range(start, len(s)):
if isPalindrome(s, start, i):
path.append(s[start:i+1])
backtrack(s, i+1)
path.pop()
res, path = [], []
backtrack(s, 0)
return res
- 优化: 动规预处理（
)：计算所有子串回文与否 (isPalindrome[i][j]: s[i], ..., s[j])
- 时间：
- 时间：
class Solution:
def partition(self, s: str) -> List[List[str]]:
def backtrack(s, start):
if start == len(s):
res.append(path[:])
return
for i in range(start, len(s)):
if isPalindrome[start][i] == True:
path.append(s[start:i+1])
backtrack(s, i+1)
path.pop()
n = len(s)
isPalindrome = [[False for _ in range(n)] for _ in range(n)]
for i in range(n-1, -1, -1): # 逆序
for j in range(i, n):
if s[i] == s[j]:
if j - i <= 1:
isPalindrome[i][j] = True
else:
isPalindrome[i][j] = isPalindrome[i+1][j-1]
res, path = [], []
backtrack(s, 0)
return res
class Solution:
def partition(self, s: str) -> List[List[str]]:
def backtrack(start):
if start == len(s):
res.append(path[:])
return
for i in range(start, len(s)):
if dp[start][i]:
path.append(s[start:i+1])
backtrack(i+1)
path.pop()
res, path = [], []
dp = [[False for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if i == j:
dp[i][j] = True
elif j - i + 1 == 2:
if s[i] == s[j]:
dp[i][j] = True
else:
dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
backtrack(0)
return res
- 进一步优化
- 动规, 记忆化搜索, 分治?
TBA
