回溯算法216|17

216组合总和III

class Solution:
    def __init__(self):
        self.result = []
        self.path = []

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.backTracking(k, n, 1)
        return self.result
        
    def backTracking(self, k, n, start_index) -> List:
        if sum(self.path) > n:
            return
        if len(self.path) == k and sum(self.path) == n:
            self.result.append(self.path[:])
        for i in range(start_index, 11 - k + len(self.path)):
            self.path.append(i)
            self.backTracking(k, n, i + 1)
            self.path.pop()

17电话号码的字母组合

class Solution:
    def __init__(self):
        self.letters = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        self.str = ""
        self.result = []

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return self.result
        self.backTracking(digits, 0)
        return self.result

    def backTracking(self, digits, index) -> List:
        if (len(self.str) == len(digits)):
            self.result.append(self.str)
            return
        digit = int(digits[index])
        letter = self.letters[digit]
        for item in letter:
            self.str += item
            self.backTracking(digits, index + 1)
            self.str = self.str[:-1]