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

一、LeetCode216. 组合总和 III

        1：题目描述（216. 组合总和 III）

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

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

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

        2：解题思路

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        path = []
        def combination(n, k, startsize):
            if len(path) == k:
                # 当path的长度等于k时，判断path中的元素和是否等于n
                if sum(path) == n:
                    # 元素之和等于n，则将path加入到res中，并返回到上一层
                    res.append(path[:])
                    return 
                # 元素之和不等于n就直接向上返回，去遍历下一个元素
                return
            # 减枝，根据k，和path的长度可以知道每层遍历最多能遍历到那个地方
            size = 9-(k-len(path))+1
            # 每次遍历从startsize开始，size结束，因为range()函数，左闭右开，所以为size+1
            for i in range(startsize,size+1):
                path.append(i)
                combination(n, k, i+1)
                # 回溯
                path.pop()
        combination(n, k, 1)
        return res

二、LeetCode17. 电话号码的字母组合

        1：题目描述（17. 电话号码的字母组合）

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

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

        2：解题思路

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []             # 存放结果的数组
        path = []            # 存放每个组合
        # 定义每个数字对应的字母
        nums_dict = {
            "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"]
        }
        s_len = len(digits)        # 获取字符串的长度，字符串的长度就是每个组合的长度
        def combinations(digits, s_len):
            if len(path) == s_len:
                if s_len == 0:
                    # 当s_len=0,说明digits为空，则直接返回
                    return 
                # 字符串digits不为空，当path的长度等于字符串digits的长度
                # 就将path中的字符，组合成一个新的字符串，加入到res中，然后返回上层
                s = "".join(path)
                res.append(s)
                return
            nums_str = digits[0]      # 取当前遍历的数字字符串
            digits = digits[1:]       # digits赋值为剩下的字符串
            nums_list = nums_dict[nums_str]     # 从nums_dict中获取当前数字对应的字母
            for i in nums_list:       # 开始遍历当前数字对应的字母列表
                path.append(i)        # 把遍历到的字母加入path中
                combinations(digits, s_len)        # 进行下一层的遍历
                # 回溯，将已加入到path中，符合要求的字母从path中弹出
                path.pop()
        combinations(digits, s_len)
        return res