代码随想录算法训练营day25|216.组合总和III

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

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

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        self.backtracking(n,k,1,[],result)
        return result
    
    def 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 result
    
    def backtracking(self,n,k,startIndex,path,result):
        if sum(path)>n: #优化，当sum(path)>n的时候，就不往下递归了
            return
        if 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.result
       
    
    def 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指向的数字转为int
        letters = self.letterMap[digit] #取数字对应的字符集
        for i in range(len(letters)):
            self.s += letters[i]
            self.back(digits,index+1) #下一层递归，需要取digits下一个数字所对应的字符集
            self.s -= letters[i] #回溯