跟77题差不多，要搞清楚k确定了递归的深度 

依旧用回溯三部曲，就是终止条件多了

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:result = []self.backtracking(n,k,1,[],result)return resultdef backtracking(self,n,k,startIndex,path,result):if len(path) == k and sum(path) == n:result.append(path[:])for i in range(startIndex,10): path.append(i)self.backtracking(n,k,i+1,path,result)path.pop()

剪枝优化

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:result = []self.backtracking(n,k,1,[],result)return resultdef backtracking(self,n,k,startIndex,path,result):if sum(path)>n: #优化，当sum(path)>n的时候，就不往下递归了returnif len(path) == k and sum(path) == n:result.append(path[:])for i in range(startIndex,9-(k-len(path))+2): #优化path.append(i)self.backtracking(n,k,i+1,path,result)path.pop()

这道题与上一题的区别在于，本题是在两个集合里面取数，把两个集合里面的元素进行组合。

例如：输入："23"，抽象为树形结构，如图所示：

 首先用二维数组进行映射，result用来储存最终结果，s用来储存每次路径走完时收集到的结果

def __init__(self):self.letterMap = ["",     # 0"",     # 1"abc",  # 2"def",  # 3"ghi",  # 4"jkl",  # 5"mno",  # 6"pqrs", # 7"tuv",  # 8"wxyz"  # 9]self.result = []self.s = ""

确定终止条件：递归的深度就是digits的长度

代码如下：

class Solution:def __init(self):self.letterMap=['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']self.result = []self.s = ''def letterCombinations(self, digits: str) -> List[str]:self.back(digits,0)return self.resultdef back(self,digits,index):#终止条件if index == len(digits): #或者 if len(self.s) == len(digits):self.result.append(self.s)return#递归逻辑digit = int(digits[index]) #将index指向的数字转为intletters = self.letterMap[digit] #取数字对应的字符集for i in range(len(letters)):self.s += letters[i]self.back(digits,index+1) #下一层递归，需要取digits下一个数字所对应的字符集self.s -= letters[i] #回溯