代码随想录算法训练营Day25|leetcode216 组合总和III，leetcode17 电话号码的字母组合

leetcode216 组合总和III

题目链接：216. 组合总和 III - 力扣（LeetCode）

视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili

文章讲解：代码随想录 (programmercarl.com)

思路：跟昨天的题很像，定义一个一维数组存单条路径结果，定义一个二维数组存所有结果，定义一个sum记录当前和，start_index记录下一次回溯开始的地方。 这里可以有一个剪枝操作，如果在path里还没到k个数但是总和已经大于目标和了就可以直接返回。

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

 leetcode17 电话号码的字母组合

题目链接：17. 电话号码的字母组合 - 力扣（LeetCode）

视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili

文章讲解：代码随想录 (programmercarl.com)

s思路，本题重点是将数字映射成字母。有点没懂，回头再看一遍 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return self.result
        self.backtracking(digits, 0)
        return self.result
        
    def __init__(self):
        self.leeterMap = [
            "",          #0
            "",          #1
            "abc",       #2
            "def",       #3
            "ghi",       #4
            "jkl",       #5
            "mno",       #6
            "pqrs",      #7
            "tuv",       #8
            "wxyz",      #9
        ]
        self.result = []
        self.s = ""
        
 
    def backtracking(self, digits, index):
        if index == len(digits):
            self.result.append(self.s)
            return
 
        digit = int(digits[index])      #将索引处的数字转化为整数
        letters = self.leeterMap[digit]  #将数字转化为对应字母
        for i in range(len(letters)):
            self.s += letters[i]
            self.backtracking(digits, index + 1)
            self.s = self.s[:-1]