216.组合总和III
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
self.tracebacking(n, k, 1, 0, [], res)
return res
def tracebacking(self, targetsum, k, start, now_sum, path, res):
if now_sum > targetsum:
return
if len(path) == k:
if targetsum == now_sum:
res.append(path[:])
return
for i in range(start, 9-(k-len(path))+2):
path.append(i)
now_sum += i
self.tracebacking(targetsum, k, i+1, now_sum, path, res)
now_sum -= i
path.pop()
17.电话号码的字母组合
class Solution:
num_dict = {
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz"
}
def letterCombinations(self, digits: str) -> List[str]:
res = []
if not digits:
return res
self.tracebacking(digits, 0, [], res)
return res
def tracebacking(self, digits, start_index, path, res):
if len(path) == len(digits):
res.append("".join(path[:]))
return
digit_int = int(digits[start_index])
letters = self.num_dict.get(digit_int)
for letter in letters:
path.append(letter)
self.tracebacking(digits, start_index+1, path, res)
path.pop()