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

216. 组合总和III

题目链接 | 解题思路

和 77 的组合其实非常相似，甚至这道题中的宽度是固定的（1-9）。需要注意的是，我的解法中使用了 sum() 来直接求解当前记录的和，如果是传递参数的方式来记录当前和，要记得在回溯的时候也把当前和进行回溯。

• 终止条件：k=0，即当前子集已经取到了 k 个元素，检查当前子集和即可
• 参数和返回值：两个全局变量，一个记录当前子集，一个记录符合条件的结果；一个额外变量传递当前的搜索起始位置
• 单层搜索：遍历当前的范围，处理-递归-回溯

class Solution:
    def __init__(self):
        self.curr_record = []
        self.results = []
    
    def backtrack(self, start: int, n: int, k: int):
        if k == 0:
            if sum(self.curr_record) == n:
                self.results.append(self.curr_record.copy())
            return None

        for i in range(start, 10):
            self.curr_record.append(i)
            self.backtrack(i + 1, n, k - 1)
            self.curr_record.pop()

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.backtrack(1, n, k)
        return self.results
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这里可行的优化有两种：

• 和 77 题一样，当剩下的搜索范围不足 k 个元素时，不必再进行搜索，也就是对 for loop 的终点进行优化
• 如果当前子集的和已经超过了要求，那自然也是不必继续递归，直接结束即可

17. 电话号码的字母组合

题目链接 | 解题思路

本题每一个数字代表的是不同集合，也就是求不同集合之间的组合。这和之前的题求解同一集合中的不同组合不一样。

• 终止条件：已经遍历过 digits 中的所有数字
• 参数和返回值：两个全局变量，一个记录当前子集，一个记录符合条件的结果；一个额外变量传递当前的数字，然后根据当前数字所对应的字母进行遍历（和之前的起始点含义不同了）
• 单层搜索：遍历当前的范围，处理-递归-回溯

class Solution:
    def __init__(self):
        self.phones = {'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']}
        self.curr_letter_record = []
        self.results = []

    def backtrack(self, letters: List[str]):
        if len(letters) == 0:
            self.results.append("".join(self.curr_letter_record))
            return None
        
        letter = letters[0]
        for digit in self.phones[letter]:
            self.curr_letter_record.append(digit)
            self.backtrack(letters[1:])
            self.curr_letter_record.pop()

    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        self.backtrack(digits)
        return self.results 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29