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

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

题目

216.组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        self.backtracking(9, k, n, 1, [], res)
        return res
    
    def backtracking(self, n, k, sum_, starIndex, curPath, res):
        if sum(curPath) > sum_:return 
        if len(curPath) == k:
            if sum(curPath) == sum_:
                res.append(curPath[:])
            return
        '''
        把前面的两个判断写成这样会造成递归太深，无论是否满足等于结果，
        只要组合有三个数都必须返回
        if len(curPath) == k and sum(curPath) == sum_:
            res.append(curPath[:])
            return 
        '''
        for i in range(starIndex, n - (k - len(curPath)) + 2):
            curPath.append(i)
            self.backtracking(n, k, sum_, i+1, curPath, res)
            curPath.pop()

题目

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

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 = []
        self.s = ""

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

    def backtracking(self, starIndex, digits, k):
        if k == len(self.s):
            self.result.append(self.s)
            return 
        curIndex = int(digits[starIndex-1])
        letterStr = self.letterMap[curIndex]
        for i in letterStr:
            self.s += i
            self.backtracking(starIndex+1, digits, k)
            self.s = self.s[:-1]