今日任务：
1）216.组合总和III
2）17.电话号码的字母组合
216.组合总和III
题目链接：216. 组合总和 III - 力扣（LeetCode）
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
文章讲解：代码随想录 (programmercarl.com)
视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III哔哩哔哩bilibili
思路：
不难，很好想，采用回溯。注意细节
采用一变量历记录差值，注意回溯，剪枝
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
self.path = []
self.result = []
self.traversal(k, n, 1)
return self.result
def traversal(self, k, div, start):
# 终止条件：当前路径长度等于 k
if len(self.path) == k:
# 如果剩余目标值为 0，且路径长度等于 k，将路径加入结果中
if div == 0:
self.result.append(self.path[:])
return
# 递归层：错去写法
# while start <= div:
# # 递归调用
# self.path.append(start)
# start += 1
# self.traversal(k, div - start + 1, start) # div用的隐藏回溯
# self.path.pop() # 回溯
# 递归层
for i in range(start, 10): # 从当前起始值到 9 进行遍历
# 提前剪枝：如果剩余目标值小于当前起始值，直接返回
if div < i:
return
# 递归调用
self.path.append(i)
self.traversal(k, div - i, i + 1) # 更新剩余目标值为 div - i，起始值为 i + 1
self.path.pop() # 回溯感想：
代码中有一个错误写法，我不能简单用差值作为遍历的终点，因为数字只能1-9，差值可能比9大，所以后面改正了
17.电话号码的字母组合
题目链接：17. 电话号码的字母组合 - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)
视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合哔哩哔哩bilibili
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
self.letterMap = [
"", # 0
"", # 1
"abc", # 2
"def", # 3
"ghi", # 4
"jkl", # 5
"mno", # 6
"pqrs", # 7
"tuv", # 8
"wxyz" # 9
]
self.path = []
self.result = []
if not digits:
return []
self.traversal(digits,0)
return self.result
def traversal(self,digits,index):
if index == len(digits):
self.result.append(''.join(self.path[:]))
return
letter = self.letterMap[int(digits[index])]
size = len(letter)
for i in range(size):
self.path.append(letter[i])
self.traversal(digits,index+1)
self.path.pop()这是没有隐藏回溯的方法
下面我们补充隐藏回溯的方法
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 映射每个数字对应的字符集合
self.letterMap = [
"", # 0
"", # 1
"abc", # 2
"def", # 3
"ghi", # 4
"jkl", # 5
"mno", # 6
"pqrs", # 7
"tuv", # 8
"wxyz" # 9
]
self.result = []
if not digits:
return []
self.traversal(digits,0,'')
return self.result
def traversal(self,digits,index,path):
"""
递归函数，用于遍历数字对应的字符集合，并生成组合
Args:
digits: 输入的数字字符串
index: 当前数字的索引
path: 当前已经生成的组合
"""
# 如果当前组合已经遍历完所有数字，则将当前组合添加到结果列表中并返回
if index == len(digits):
self.result.append(path)
return
# 获取当前数字对应的字符集合
letter = self.letterMap[int(digits[index])]
size = len(letter)
# 遍历当前数字对应的字符集合
for i in range(size):
# 递归调用深度优先搜索函数，遍历下一个数字的字符集合
self.traversal(digits,index+1,path + letter[i])
