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

今日任务：

LeetCode216 组合总和Ⅲ
LeetCode17 电话号码的字母组合

资料来源：

1 LeetCode216 组合总和Ⅲ

题目

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

只使用数字1到9 每个数字最多使用一次返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:


输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:


输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:


输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

2 <= k <= 9
1 <= n <= 60

回溯秒了。

python
from typing import List

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

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.target_sum = n
        self.target_length = k
        self.resursion(0)
        return self.result

    def resursion(self, num_added: int):
        if sum(self.path) == self.target_sum and len(self.path) == self.target_length:
            self.result.append(self.path.copy())
            return
        for i in range(num_added + 1, 10):
            self.path.append(i)
            self.resursion(i)
            self.path.pop()
        return

和昨天的题一样，可以剪枝。

python
# 剪枝版本
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def __init__(self):
        self.path = []
        self.target_sum = 0
        self.target_length = 0
        self.result = []

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.target_sum = n
        self.target_length = k
        self.resursion(0)
        return self.result

    def resursion(self, num_added: int):
        if len(self.path) > self.target_length:
            return
        if sum(self.path) == self.target_sum and len(self.path) == self.target_length:
            self.result.append(self.path.copy())
            return
        # 剪枝 1 目前已经有多长 len(self.path)
        # 2 目前还需要多长 self.target_length - len(self.path)
        # 3 所以循环到什么位置 range(num_added + 1, 10 - (self.target_length - len(self.path)))
        for i in range(num_added + 1, 10 - (self.target_length - len(self.path)) + 1):
            self.path.append(i)
            self.resursion(i)
            self.path.pop()
        return

2 LeetCode17 电话号码的字母组合

题目

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

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

示例 1：


输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：


输入：digits = ""
输出：[]

示例 3：


输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

回溯一样秒。先建立数字到字符串的映射（可以优化为数组），按传入的字符串长度决定递归深度，每个数字对应的字母数量决定for次数，最后递归回来记得回溯就行。

提示

python做传列表参数或者两个列表互相append的时候如果出问题，优先考虑要不要copy。

python
from typing import List

class Solution:
    def __init__(self):
        self.map = {2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
        self.path = []
        self.result = []
        self.digits = []

    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        self.digits = list(digits)
        self.recursion(0)
        result_ = []
        for i in self.result:
            result_.append("".join(i))
        return result_

    def recursion(self, index: int):
        if index == len(self.digits):
            self.result.append(self.path.copy())
            return
        chars = self.map.get(int(self.digits[index]))
        for i in chars:
            self.path.append(i)
            self.recursion(index + 1)
            self.path.pop()

目录

1 LeetCode216 组合总和Ⅲ

2 LeetCode17 电话号码的字母组合