216. 组合总和 III
【注意】
1.组合不强调元素之间的顺序。
【代码】
1 class Solution(object): 2 def __init__(self): 3 self.res = [] 4 self.sum_now = 0 5 self.path = [] 6 def combinationSum3(self, k, n): 7 """ 8 :type k: int 9 :type n: int 10 :rtype: List[List[int]] 11 """ 12 self.backtracking(k, n, 1) 13 return self.res 14 15 def backtracking(self, k, n, start_num): 16 if self.sum_now > n: # 剪枝 17 return 18 if len(self.path) == k: # len(path)==k时不管sum是否等于n都会返回 19 if self.sum_now == n: 20 self.res.append(self.path[:]) 21 return 22 for i in range(start_num, 10 - (k - len(self.path)) + 1): 23 self.path.append(i) 24 self.sum_now += i 25 self.backtracking(k, n, i + 1)#递归 26 #回溯 27 self.path.pop() 28 self.sum_now -= i
17. 电话号码的字母组合
【注意】
1.index是记录遍历第几个数字了,就是用来遍历digits的(题目中给出数字字符串),同时index也表示树的深度。
【代码】
1 class Solution(object): 2 def __init__(self): 3 self.answers = [] 4 self.answer = '' 5 self.letter_map = { 6 '2': 'abc', 7 '3': 'def', 8 '4': 'ghi', 9 '5': 'jkl', 10 '6': 'mno', 11 '7': 'pqrs', 12 '8': 'tuv', 13 '9': 'wxyz' 14 } 15 def letterCombinations(self, digits): 16 """ 17 :type digits: str 18 :rtype: List[str] 19 """ 20 if not digits: 21 return [] 22 self.backtracking(digits, 0) 23 24 return self.answers 25 26 def backtracking(self, digits, index): 27 if index == len(digits): 28 self.answers.append(self.answer) 29 return 30 31 letters = self.letter_map[digits[index]] 32 for letter in letters: 33 self.answer += letter 34 self.backtracking(digits, index+1) 35 self.answer = self.answer[:-1] # 回溯 36 print(self.answer)
标签:216,digits,index,self,随想录,backtracking,字母组合,path,def From: https://www.cnblogs.com/wuyijia/p/17455563.html