class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []    #save the result
        self.backtracking(n, k, 0, 1, [], result)
        return result

    def backtracking(self, targetSum, k, currentSum, startIndex, path,result):
        if currentSum > targetSum:      #cutting the branch
            return
        if len(path) == k:
            if currentSum == targetSum:
                result.append(path[:])
            return
        for i in range(startIndex, 9-(k-len(path))+2):      #cutting branch
            currentSum += i     #process the node
            path.append(i)      #process the node
            self.backtracking(targetSum, k, currentSum, i+1, path,result)
            currentSum -= i     #backtracking
            path.pop()      #backtracking

class Solution:
    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 = []    #define a global variable to store all results
        self.s = ""     #define a global variable to store each string

    def backtracking(self, digits, index):
        if index == len(digits):
            self.result.append(self.s)
            return
        digit = int(digits[index])     #change number in digits from string input to real number
        letters = self.letterMap[digit]     #get the corresbonding letters for this digit
        for i in range(len(letters)):
            self.s += letters[i]        #add the letter to result string
            self.backtracking(digits, index+1)      #recursion, deal with the next number given in the digits
            self.s = self.s[:-1]    #backtracking, delete the last item added to the result string

    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return self.result
        self.backtracking(digits, 0)
        return self.result