216.组合总和III

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        
        path = []
        result = []
        def backtracking(n, k, sum_num, start_index):
            # 剪枝，如果sum_num 大于tagget n，返回
            if sum_num > n:
                return
            # 收获结果，满足 和为n的k个数的组合
            if len(path) == k:
                if sum_num == n:
                    result.append(path[:])
                return
            for i in range(start_index, 10 - (k - len(path)) + 1):
                path.append(i)
                sum_num += i
                backtracking(n, k, sum_num, i + 1)
                path.pop()
                sum_num -= i
        backtracking(n, k, 0, 1)
        return result

17.电话号码的字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:

        letter_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        s = ""
        result = []
        if digits == "":
            return result
        def backtracking(digits, index): #index 遍历到的数字
            nonlocal s
            if index == len(digits):
                result.append(s)
                return
            letters = letter_map[digits[index]]
            for i in letters:
                s += i
                backtracking(digits, index + 1)
                s = s[:-1]
        backtracking(digits, 0)
        return result