題目簡介
216. 組合總和 III
找出所有相加之和為 n 的 k 個數(shù)的組合分瘦，且滿足下列條件：
只使用數(shù)字1到9
每個數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 油湖。該列表不能包含相同的組合兩次昭殉，組合可以以任何順序返回。
17. 電話號碼的字母組合
給定一個僅包含數(shù)字 2-9 的字符串冬殃，返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數(shù)字到字母的映射如下（與電話按鍵相同）辐怕。注意 1 不對應(yīng)任何字母。
初見思路
- 使用標(biāo)準(zhǔn)回溯贡茅，會直接超時, 以及眼瞎秘蛇，沒有看見只能使用數(shù)字1-9
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
self.combinations = list()
self.routes = list()
self.n = n
nums = list(range(n))
self.back_track(nums,1,k)
return self.combinations
def back_track(self,nums: List[int],index:int,k:int) -> None:
if len(self.routes) == k and sum(self.routes) == self.n:
self.combinations.append(list(self.routes))
else:
for i in range(index,len(nums)):
self.routes.append(nums[i])
self.back_track(nums, i + 1, k)
self.routes.pop()
更正后擊敗了93%
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
self.combinations = list()
self.routes = list()
self.n = n
nums = list(range(10))
self.back_track(nums,1,k)
return self.combinations
def back_track(self,nums: List[int],index:int,k:int) -> None:
if sum(self.routes) > self.n:
return
if len(self.routes) == k and sum(self.routes) == self.n:
self.combinations.append(list(self.routes))
else:
for i in range(index,10):
self.routes.append(nums[i])
self.back_track(nums, i + 1, k)
self.routes.pop()
- 構(gòu)建按鍵到字母的字典，對于每次到一個新的數(shù)字顶考，對字典中對應(yīng)的字母進(jìn)行組合赁还。
class Solution:
def __init__(self):
self.s = ""
self.button_map = {
"0":"",
"1":"",
"2":"abc",
"3":"def",
"4":"ghi",
"5":"jkl",
"6":"mno",
"7":"pqrs",
"8":"tuv",
"9":"wxyz"
}
self.ans = list()
def back_tracking(self,digits:str,index:int)-> None:
if index == len(digits):
self.ans.append(self.s)
return
letters = self.button_map[digits[index]]
for i in range(len(letters)):
self.s += letters[i]
self.back_tracking(digits, index+1)
self.s = self.s[:-1]
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return list()
self.back_tracking(digits,0)
return self.ans
復(fù)盤思路
https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html
