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

216.组合总和III

文档讲解:代码随想录

题目链接：. - 力扣（LeetCode）

这一题与昨天的组合差不多，区别就在只有和是目标值的时候才会加入到result数组中，并且在回溯时，会处理sum的值

class Solution:def __init__(self):# 初始化路径self.path = []# 初始化结果集self.result = []def combinationSum3(self, k: int, n: int) -> List[List[int]]:def backtracking(start_index, k, n, sum):# 如果路径长度等于kif len(self.path) == k:# 如果路径和等于n，将路径加入结果集if sum == n:self.result.append(copy.deepcopy(self.path)) # 深拷贝结果return # 从[start_index, 10)范围内选择数字，因为数字范围是1-9for i in range(start_index, 10):# 将当前数字加入路径self.path.append(i)# 更新路径和sum += i# 递归进入下一层，传入更新后的start_indexbacktracking(i+1, k, n, sum)# 回溯，将当前数字从路径中移除，并将路径和减去当前数字sum -= iself.path.pop()# 调用回溯函数，起始数字从1开始backtracking(1, k, n, 0)return self.result

17.电话号码的字母组合

文档讲解：代码随想录

题目链接：. - 力扣（LeetCode）

理解本题后，要解决如下三个问题：

1. 数字和字母如何映射
2. 两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
3. 输入1 * #按键等等异常情况

数字和字母如何映射

定义一个字符串列表，列表中的每一项都是字符串，下标就对应着数字

letterMap[10] = ["", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9
]

回溯法来解决n个for循环的问题

虽然回溯算法也是暴力的，但是他通过递归的方式来帮我们嵌套了我们想实现的for循环

回溯法

回溯函数参数返回值和参数：

首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量依然定义为全局。

再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index。

注意这个index可不是 77.组合 (opens new window)和216.组合总和III (opens new window)中的startIndex了。

这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。之前的题目是在一个列表中求组合，就不可以重复，需要startindex来帮助我们避免重复，这一题是在两个列表中组合，所以不会有重复的

回溯函数终止条件

例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。

那么终止条件就是如果index 等于 输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。

然后收集结果，结束本层递归。

回溯搜索的单层搜索逻辑

首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。

然后for循环来处理这个字符集。

代码如下：

class Solution:def __init__(self):# 定义全局变量self.str = ''  # 用于存储当前组合的字符串self.result = []  # 用于存储所有可能的组合# 定义数字到字母的映射表self.letter_map = ["",     # 0"",     # 1"abc",  # 2"def",  # 3"ghi",  # 4"jkl",  # 5"mno",  # 6"pqrs", # 7"tuv",  # 8"wxyz"  # 9]def letterCombinations(self, digits: str) -> List[str]:# 将输入的数字字符串转换成列表digits = list(digits)# 定义回溯函数def backtracking(digits, index):# 如果当前索引等于输入数字的长度，表示已生成一个完整的组合if index == len(digits):# 将当前组合的字符串深拷贝后添加到结果列表中self.result.append(self.str[:])return# 获取当前数字对应的字母集合digit = int(digits[index])for i in self.letter_map[digit]:# 将当前字母添加到组合字符串中self.str += i# 递归调用回溯函数处理下一个数字backtracking(digits, index + 1)# 回溯，移除当前添加的字母self.str = self.str[:-1]# 返回最终的结果列表return self.result# 如果输入数字字符串为空，直接返回空结果if len(digits) == 0:return self.result# 调用回溯函数从第一个数字开始处理return backtracking(digits, 0)