题目简介
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
初见思路
- 使用标准回溯，会直接超时, 以及眼瞎，没有看见只能使用数字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()
- 构建按键到字母的字典，对于每次到一个新的数字，对字典中对应的字母进行组合。
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
复盘思路
https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html
