39. 組合總和
- 思路
- example
- 回溯：深度由sum_ vs target控制枝恋，寬度由startIndex控制。
- candidates中無重復(fù)元素
- 不需要考慮同層去重
- 無限制重復(fù)被選取 （有放回）
- startIndex取當(dāng)前位置
- "去重“：排序 + startIndex
無重可復(fù)選
注意：本題不需預(yù)先排序锌仅。
- 剪枝
- 模向 （for 循環(huán)內(nèi)）
- 縱向 （遞歸函數(shù)base case)
- 2 <= candidates[i] <= 40
- 復(fù)雜度. 時間：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) # !!! 可重復(fù)取
path.pop()
res, path = [], []
backtrack(0)
return res
- 另一種寫法
- 深度：逐個遍歷candidates
- 寬度：每個candidate選取可能性：0大刊，1劳景，2，。蝙搔。钓辆。
TBA
40. 組合總和 II
- 思路
- example
- candidates有重復(fù)元素
- 同層去重
if i > start and candidates[i] == candidates[i-1]:
continue
- candidates 中的每個數(shù)字在每個組合中只能使用 一次
- 復(fù)雜度. 時間：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中有重復(fù)
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數(shù)組）
image - 復(fù)習(xí) 216. 組合總和 III
- 無重不可復(fù)選
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
-
小結(jié)：組合
- 去重 （sort, startIndex)
- 剪枝
- 個數(shù)
- target, sum_, ...
- 有放回 vs 無放回
- startIndex: i vs i + 1
-
桶裝球 vs 球裝桶
- 桶的限制剪验？球的限制？
- 桶裝球：桶視角前联。深度=桶功戚，寬度=球（可選范圍，規(guī)格似嗤，限制啸臀，每次選一個球）
- 球裝桶：球視角。深度=球烁落，寬度=桶（桶的體積乘粒，規(guī)格，限制伤塌，可能取多個球）
131. 分割回文串
- 思路
- example
- 返回 s 所有可能的分割方案: 暴力回溯谓厘。
- 切割 （轉(zhuǎn)化為組合問題）
-
判斷回文 （雙指針）
- 暴力回溯：
- 桶裝球
- 深度：切割位置 （子串起始位置startIndex），桶
- 寬度：切割位置 （子串結(jié)束位置）寸谜，球
- 復(fù)雜度. 時間：
, 空間:
- worst case: s = ‘a(chǎn)aaaaaaaa’
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
- 優(yōu)化: 動規(guī)預(yù)處理（
)：計算所有子串回文與否 (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
- 進一步優(yōu)化
- 動規(guī), 記憶化搜索, 分治?
TBA
