216 组合总和III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9；每个数字 最多使用一次 ；
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
def combineSum3(k:int,n:int)->'ListList[int]'
result=[]
def backtracking(targetSum,k,currentSum,startIndex,path,result):
if currentSum>targetSum:
return
if len(path)==k:
if currentSum==targetSum:
result.append(path[:])
return
for i in range(startIndes,9-(k-len(path))+2):
currentSum+=i
path.append(i)
backtracking(targetSum,k,currentSum,i+1,path,result)
currentSum-=i
path.pop()
17 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
思路
根据index获取digits中的一个digit，根据digit作索引找到letterMap对应letters，遍历（取一个letter，递归第二个digit…直到digits全部对应，加入到result中）
letterMap=['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
def backtracking(digits,index):
if index==len(digits):
result.append(s)
return
digit=int(digits[index])
letters=letterMap[digit]
for i in range(len(letters)):
s+=letters[i]
backtracking(digits,index+1)
s=s[:-1]
def letterCombinations(digits:'str')->'List[str]':
result=[]
s=''
if len(digits)=0:
return []
backtracking(digits,index=0)
return result
