25天【代码随想录算法训练营34期】第七章 回溯算法part02 （ ● 216.组合总和III ● 17.电话号码的字母组合）

**216.组合总和III **

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

17.电话号码的字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        map_ = {'2':['a', 'b', 'c'], '3':['d', 'e', 'f'], '4':['g', 'h', 'i'], '5':['j', 'k', 'l'], '6':['m', 'n', 'o'], '7':['p', 'q', 'r', 's'],'8':['t', 'u', 'v'], '9':['w', 'x', 'y', 'z']}
        result = []
        digitsLetterList = []
        for i in digits:
            digitsLetterList.append(map_[i])
        self.backtracking(0, digitsLetterList, [], result, len(digits))
        return result

    def backtracking(self, startingIndex, digitsLetterList, path, result, len_):
        if len(path) == len_:
            if len(path) > 0:
                result.append(''.join(path))
            return
        for i in range(len(digitsLetterList[startingIndex])):
            path.append(digitsLetterList[startingIndex][i])
            self.backtracking(startingIndex+1, digitsLetterList, path, result, len_)
            path.pop()