代码随想录算法训练营day25 | 216.组合总和III、17.电话号码的字母组合

216.组合总和III

未剪枝，和组合题目类似

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

    def backtracking(self, k, n, startIndex):
        if len(self.path) == k:
            if sum(self.path) == n:
                self.result.append(self.path[:])
            else:
                return
        for i in range(startIndex, 10):
            self.path.append(i)
            self.backtracking(k, n, i+1)
            self.path.pop()

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.backtracking(k, n, 1)
        return self.result

剪枝，并且优化了求和操作

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

    def backtracking(self, k, n, sum, startIndex):
        if sum > n:
            return
        if len(self.path) == k:
            if sum == n:
                self.result.append(self.path[:])
            else:
                return
        for i in range(startIndex, 9-(k-len(self.path))+2):
            self.path.append(i)
            sum += i
            self.backtracking(k, n, sum, i+1)
            self.path.pop()
            sum -= i

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.backtracking(k, n, 0, 1)
        return self.result

17.电话号码的字母组合

没做出来，看题解学习

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


    def backtracking(self, digits, index):
        if len(digits) == index:
            self.result.append(self.s)
            return

        for i in self.letterMap[int(digits[index])]:
            self.s += i
            index += 1
            self.backtracking(digits, index)
            index -= 1
            self.s = self.s[:-1]

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

结果字符改为列表

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


    def backtracking(self, digits, index):
        if len(digits) == index:
            self.result.append("".join(self.s))
            return

        for i in self.letterMap[int(digits[index])]:
            self.s.append(i)
            self.backtracking(digits, index+1)
            self.s.pop()

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