39. 组合总和
【注意】
1.candidates 中的数字可以无限制重复被选取。
2.在for循环中进行剪枝。剪枝前需要对数组进行排序。
【代码】
1 class Solution(object): 2 def __init__(self): 3 self.path = [] 4 self.paths = [] 5 6 def combinationSum(self, candidates, target): 7 """ 8 :type candidates: List[int] 9 :type target: int 10 :rtype: List[List[int]] 11 """ 12 #为了剪枝需要提前进行排序 13 candidates.sort() 14 #递归 15 self.backtracking(candidates, target, 0, 0) 16 return self.paths 17 18 def backtracking(self, candidates, target, sum_, start_index): 19 #停止条件 20 if sum_ == target: 21 self.paths.append(self.path[:]) 22 # 单层递归逻辑 23 # 如果本层 sum + condidates[i] > target，就提前结束遍历，剪枝 24 for i in range(start_index, len(candidates)): 25 if sum_ + candidates[i] > target: 26 return 27 sum_ += candidates[i] 28 self.path.append(candidates[i]) 29 # 因为无限制重复选取，所以不是i+1 30 self.backtracking(candidates,target,sum_,i) 31 #回溯 32 sum_ -= candidates[i] 33 self.path.pop()
40. 组合总和 II
【注意】
1.去重，不能出现重复的组合。搜索过程进行去重。
2.树层，树枝去重。需要排序。----关键在树层去重,在for循环里进行树层去重。
3.used[i-1]=0（树层）
【代码】
1 class Solution(object): 2 def __init__(self): 3 self.path = [] 4 self.paths = [] 5 # #1.使用used数组 6 # self.used = [] 7 def combinationSum2(self, candidates, target): 8 """ 9 :type candidates: List[int] 10 :type target: int 11 :rtype: List[List[int]] 12 """ 13 self.usage_list = [False] * len(candidates) 14 candidates.sort() 15 #递归 16 self.backtracking(candidates, target,0, 0) 17 return self.paths 18 19 def backtracking(self, candidates, target, sum_, start_index): 20 if sum_ == target: 21 self.paths.append(self.path[:]) 22 return 23 24 for i in range(start_index, len(candidates)): 25 #剪枝 26 if sum_ + candidates[i] > target: 27 return 28 # 检查同一树层是否出现曾经使用过的相同元素 29 # 若数组中前后元素值相同，但前者却未被使用(used == False)，说明是for loop中的同一树层的相同元素情况 30 if i>0 and candidates[i] == candidates[i-1] and self.usage_list[i-1] == False: 31 continue 32 sum_ += candidates[i] 33 self.path.append(candidates[i]) 34 self.usage_list[i] = True 35 self.backtracking(candidates, target,sum_, i+1) 36 self.usage_list[i] = False 37 self.path.pop() 38 sum_ -= candidates[i]
1 class Solution(object): 2 def __init__(self): 3 self.path = [] 4 self.paths = [] 5 6 def combinationSum2(self, candidates, target): 7 """ 8 :type candidates: List[int] 9 :type target: int 10 :rtype: List[List[int]] 11 """ 12 candidates.sort() 13 #递归 14 self.backtracking(candidates, target,0, 0) 15 return self.paths 16 17 def backtracking(self, candidates, target, sum_, start_index): 18 if sum_ == target: 19 self.paths.append(self.path[:]) 20 return 21 22 for i in range(start_index, len(candidates)): 23 #剪枝 24 if sum_ + candidates[i] > target: 25 return 26 #2.不使用used数组进去去重 27 # 跳过同一树层使用过的元素 28 if i > start_index and candidates[i] == candidates[i-1]: 29 continue 30 31 sum_ += candidates[i] 32 self.path.append(candidates[i]) 33 self.backtracking(candidates, target,sum_, i+1) 34 self.path.pop() 35 sum_ -= candidates[i]
131. 分割回文串
【注意】
1.start_index是切割线，[startIndex, i] 就是要截取的子串。
2.递归用来纵向遍历，for循环用来横向遍历。
3.判断回文串：可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。
【代码】
1 class Solution(object): 2 def __init__(self): 3 self.paths = [] 4 self.path = [] 5 6 def partition(self, s): 7 """ 8 :type s: str 9 :rtype: List[List[str]] 10 """ 11 self.backtracking(s, 0) 12 return self.paths 13 14 def backtracking(self, s, start_index): 15 if start_index >= len(s): 16 self.paths.append(self.path[:]) 17 return 18 19 # 单层递归逻辑 20 for i in range(start_index, len(s)):#横向 21 # 此次比其他组合题目多了一步判断： 22 # 判断被截取的这一段子串([start_index, i])是否为回文串 23 temp = s[start_index:i+1] 24 # print(temp) 25 if temp == temp[::-1]: # 若反序和正序相同，意味着这是回文串 26 self.path.append(temp) 27 self.backtracking(s, i+1) # 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串 28 self.path.pop() 29 else: 30 continue