tasks for today:
1.39.组合总和
2.40.组合总和II
3.131.分割回文串
----------------------------------------------------------
1.39.组合总和
IN this practice, the key change is the requirement that the element can be repetatively used, which can be achieved by control the startIndex in each loop of backtracking, when it is not allow to repete, the index will be i+1, but in this practice, it should be i;
but this brings the time exceeding limits issue if no cut branching is execute, this should be noted.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
path = []
self.backtracking(candidates, target, 0, path, result)
return result
def backtracking(self, candidates, target, startIndex, path, result):
# in this practice, cutting branch is important, or it will exceed the time limit
if sum(path) > target:
return
if sum(path) == target:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
path.append(candidates[i])
self.backtracking(candidates, target, i, path, result)
path.pop()
在求和问题中,排序之后加剪枝是常见的套路!
本题:(1)list不包含重复元素(2)list每个元素可以重复使用
2.40.组合总和II
本题:(1)list包含重复元素(2)list每个元素不可以重复使用(3)最终结果不包含重复组合
here if we only use "if i > 0 and candidates[i] == candidates[i - 1]:" as condition, this will cut off some circumstance that from one tree branch, instead of trimming the same level, so an additional used list recording the usage condition for each level is added as a new factor
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
candidates.sort()
path = []
used = [False] * len(candidates)
self.backtracking(candidates, target, 0, path, result, used)
return result
def backtracking(self, candidates, target, startIndex, path, result, used):
if sum(path) > target:
return
if sum(path) == target:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
# here if we only use "if i > 0 and candidates[i] == candidates[i - 1]:" as condition,
# this will cut off some circumstance that from one tree branch, instead of trimming the same level
# so an additional used list recording the usage condition for each level is added as a new factor
if i > 0 and candidates[i] == candidates[i - 1] and used[i-1] == False:
continue
path.append(candidates[i])
used[i] = True
self.backtracking(candidates, target, i + 1, path, result, used)
used[i] = False
path.pop()
Note: do not forget to sort the candidates list before doing operation
3.131.分割回文串
in this practice, the individual traversed is not a digit as previous practice, instead, it is a part of string from s, which is s[startIndex, i+1];
then another function used to judge if a string is a palindrome should be composed to check the qualification of ann individual string cut.
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
path = []
self.backtracking(s, 0, path, result)
return result
def backtracking(self, s, startIndex, path, result):
if startIndex >= len(s):
result.append(path[:])
return
for i in range(startIndex, len(s)):
s_cut = s[startIndex:i+1]
if self.isPalindrom(s_cut):
path.append(s_cut)
self.backtracking(s, i+1, path, result)
path.pop()
def isPalindrom(self, s):
left = 0
times = len(s) // 2
right = len(s) - 1
for i in range(times):
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
标签:tracking,target,7.25,self,part02,used,candidates,result,path
From: https://blog.csdn.net/bbrruunnoo/article/details/140685733