216.组合总和III
本题思路和 77. 组合 类似，在此基础上多了一个和为 n 的判断。
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtrack(start, path, currentSum):
# 递归终止条件：到达叶子节点
# 如果和满足条件，则收集后终止，否则直接终止
if len(path) == k:
if currentSum == n:
result.append(path[:])
return
for num in range(start, 9 + 1):
currentSum += num
path.append(num)
backtrack(num + 1, path, currentSum)
path.pop()
currentSum -= num
result = []
backtrack(start = 1, path = [], currentSum = 0)
return result本题有两个地方可以剪枝：
- 当前组合元素的 和 超过要求
- 当前组合元素的 数量 超过要求
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtrack(start, path, currentSum):
# 剪枝1: 和超过要求
if currentSum > n:
return
if len(path) == k:
if currentSum == n:
result.append(path[:])
return
# 剪枝2: 组合元素数量超过要求
for num in range(start, 9 - (k - len(path)) + 1 + 1):
currentSum += num
path.append(num)
backtrack(num + 1, path, currentSum)
path.pop()
currentSum -= num
result = []
backtrack(start = 1, path = [], currentSum = 0)
return result17.电话号码的字母组合
本题相当于从每个数字对应的字母中构建结果，我们需要借助一个 index 来跟踪数字。由于每个数字对应的字母都没有重复，因此每个结果都符合题意，不需要剪枝。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
phoneMap = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
def backtrack(index, path):
# 递归结束条件
# 当组合的长度等于输入数字的长度，收集结果
if len(path) == len(digits):
result.append(''.join(path))
return
# 获取当前数字所对应的所有可能字母
possible_letters = phoneMap[digits[index]]
# 遍历这些字母，递归构造剩余的组合
for letter in possible_letters:
path.append(letter)
backtrack(index + 1, path)
path.pop()
result = []
backtrack(index = 0, path = [])
return result
