77. 组合
目标：
给定两个整数n和k，返回[1, n]中所有可能的k个数的组合。
- 组合：只关心选了哪些数
- 不关心顺序：
[1,2]和[2,1]是同一个组合
核心思路
这是一个经典回溯 / DFS 组合题。
为什么用回溯？
我们在做的是：
👉从 1~n 中“选 k 个”每个数：
- 要么选
- 要么不选
但为了避免重复（比如
[2,1]），必须保证递增顺序
回溯模型（记这个模板）
路径 path：当前已经选的数 起点 start：下一步可以选的最小数字（保证不回头） 终止条件：path 长度 == k决策过程:
- 在
[start, n]范围内枚举下一个数字 - 对每个数字：
- 选择它，加入
path - 递归继续选择下一个（
start更新为当前数字 + 1） - 回溯：撤销本次选择，尝试其他数字
- 选择它，加入
代码
fromtypingimportListclassSolution:defcombine(self,n:int,k:int)->List[List[int]]:res=[]# 最终结果：存所有长度为 k 的组合path=[]# 当前正在构建的组合（回溯路径）defbacktracking(start):""" start：当前层允许选择的最小数字 保证组合中的数字递增，避免重复 """# 终止条件：已经选了 k 个数iflen(path)==k:# 注意：必须拷贝 path# 因为 path 会在回溯过程中被不断修改res.append(path[:])return# 在当前层，从 start 到 n 依次尝试每一个可能的选择foriinrange(start,n+1):# 1️⃣ 做选择：把当前数字加入路径path.append(i)# 2️⃣ 进入下一层递归# 下一层只能从 i + 1 开始选，不能回头backtracking(i+1)# 3️⃣ 撤销选择（回溯）# 把刚刚加进去的数字移除，尝试下一个 ipath.pop()# 从 1 开始尝试选第一个数backtracking(1)returnres| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(C(n, k) · k) | 一共生成 C(n, k) 个组合，每个组合拷贝 k 个元素 |
| 空间复杂度 | O(k) | 递归调用栈 + 当前 path 的最大长度 |
77剪枝做法
在已经不可能选满 k 个数的情况下，提前停止递归。
为什么 77 可以剪枝？
在某一层：
已经选了
len(path)个数还需要选：
k-len(path)而当前能用的数字是：
[start,start+1,...,n]数量是：
n-start+1❗ 如果：
剩余可选数量 < 还需要选的数量👉 这条路不可能成功，直接停
剪枝怎么体现在代码里？
原来的 for 循环
foriinrange(start,n+1):剪枝后的 for 循环（核心）
foriinrange(start,n-(k-len(path))+2):
如何理解：
我要给未来留下 足够的位置，让后面还能选满 k 个。
- 当前选
i - 后面最多还能选：
n-i所以i最大只能到：
n-(k-len(path))+1Python 的range右端不包含 → 再+1
代码
classSolution:defcombine(self,n:int,k:int):res=[]path=[]defbacktracking(start):# 如果已经选满 k 个，记录结果iflen(path)==k:res.append(path[:])return# 剪枝：# 剩余可选数量 = n - start + 1# 需要选的数量 = k - len(path)# 当剩余 < 需要时，for 循环根本不会进入foriinrange(start,n-(k-len(path))+2):path.append(i)backtracking(i+1)path.pop()backtracking(1)returnres| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(C(n, k) · k) | 最终仍然要生成所有合法组合；剪枝只是减少无效搜索路径 |
| 空间复杂度 | O(k) | 递归调用栈深度最多为 k，path长度最多为 k |
216.组合总和III
目标：
从1 到 9 中选 k 个不同的数，使它们的和等于 n，返回所有组合。
- 每个数字只能用一次
- 组合（不关心顺序）
- 数字范围固定是 1～9
核心思路
这是「固定长度 k 的组合」+「有目标和 n」
回溯设计（三要素）:
- path
- 当前选中的数字
- 同时决定：
- 已选个数
len(path) - 当前和
cur_sum
- 已选个数
- start
- 下一步允许选择的最小数字
- 保证递增，避免重复
- 终止条件
- 如果
len(path) == k：- 若
cur_sum == n→ 记录结果 - 否则 → 直接返回
- 若
- 如果
代码
fromtypingimportListclassSolution:defcombinationSum3(self,k:int,n:int)->List[List[int]]:res=[]# 存放所有满足条件的组合path=[]# 当前正在构建的组合defbacktracking(start):""" start: 当前层允许选择的最小数字 保证数字递增，避免重复使用同一个数字 """# 如果已经选了 k 个数iflen(path)==k:# 只在这里检查组合的和是否等于 nifsum(path)==n:# 必须拷贝 path，否则回溯时会被修改res.append(path[:])return# 从 start 到 9 依次尝试选择数字foriinrange(start,10):# 做选择：加入当前数字path.append(i)# 进入下一层，下一层只能选更大的数字backtracking(i+1)# 撤销选择（回溯）path.pop()# 从 1 开始尝试选第一个数字backtracking(1)returnres| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(C(9, k) · k) | 枚举所有长度为 k 的组合，每次计算sum(path)需要 O(k) |
| 空间复杂度 | O(k) | 递归调用栈深度最大为 k，path长度最多为 k |
216剪枝
✂️ 剪枝 1：和已经超过 n，直接停cur_sum > n
defbacktracking(start,cur_sum):ifcur_sum>n:# ✅ 剪枝 1return如果当前路径的和已经大于目标 n，后面只会加更大的数，不可能成功 → 直接返回。
✂️ 剪枝 2：for 循环里提前 breaklen(path) > k
foriinrange(start,10):ifcur_sum+i>n:# ✅ 剪枝 2break这行为什么是 break？
i是递增的cur_sum + i已经超了- 后面的
i+1,i+2… 只会更大
👉 这一整段 for 都没必要继续
剪枝 1 和 剪枝 2 本质上在“做同一件事”（防止和超过 n），
但作用位置不同，功能并不完全重复。
👉 实际写代码时：二选一就够了
👉 最推荐：只保留剪枝 2
✂️ 剪枝 3：剩余数量不够凑满 k
# 还需要选的数量need=k-len(path)# 剩余可选数字数量remain=9-start+1ifremain<need:# ✅ 剪枝 3return剩下的数字数量，已经不够凑满 k 个 👉 再选也没意义，直接停
代码
classSolution:defcombinationSum3(self,k:int,n:int):res=[]path=[]defbacktracking(start,cur_sum):# 🔴 剪枝 1：和已经超过 nifcur_sum>n:return# 选满 k 个数iflen(path)==k:ifcur_sum==n:res.append(path[:])return# 🔴 剪枝 3：剩余数字不够if9-start+1<k-len(path):returnforiinrange(start,10):# 🔴 剪枝 2：for 循环提前结束ifcur_sum+i>n:breakpath.append(i)backtracking(i+1,cur_sum+i)path.pop()backtracking(1,0)returnres| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(C(9, k) · k) | 枚举所有合法组合，9 是常数 |
| 空间复杂度 | O(k) | 递归深度 + path 长度 |
17.电话号码的字母组合
给一个字符串digits（只包含 2-9），每个数字对应手机九宫格字母，比如：
- 2: abc
- 3: def
- …
把所有可能的字母组合都列出来。
例："23"→["ad","ae","af","bd","be","bf","cd","ce","cf"]
空输入""→ 返回[]
核心思路（回溯/DFS）
用 dict 存数字 → 字母
2->abc3->def...从左到右处理 digits
- 第 1 个数字选一个字母
- 第 2 个数字再选一个字母
- 一直选到最后一位
每一位都把能选的字母“试一遍”
- 字符串长度够了 → 存结果
- 不够 → 继续拼
状态：
idx：当前处理到 digits 的第几位path：当前拼出来的字符串（或字符数组）
代码
fromtypingimportListclassSolution:defletterCombinations(self,digits:str)->List[str]:# 如果输入是空字符串，没有任何组合# LeetCode 要求返回 []ifnotdigits:return[]# 数字到字母的映射表（手机九宫格）phone={"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}res=[]# 最终结果：存所有字母组合path=[]# 当前正在拼的字符串（用 list，方便回溯）defbacktracking(idx):""" idx：当前处理到 digits 的第 idx 位 表示现在要给第 idx 个数字选一个字母 """# 如果已经处理完所有数字# 说明 path 中已经拼好了一个完整组合ifidx==len(digits):# 把当前拼好的字符列表转成字符串存起来res.append("".join(path))return# 取出当前数字对应的所有字母letters=phone[digits[idx]]# 依次尝试每一个字母forlinletters:# 1️⃣ 选择：把当前字母加入 pathpath.append(l)# 2️⃣ 进入下一位数字backtracking(idx+1)# 3️⃣ 撤销选择（回溯）# 换下一个字母继续试path.pop()# 从第 0 位数字开始处理backtracking(0)returnres| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(4^m · m) | 一共有最多4^m种字母组合，每个组合长度为m，需要拼接成字符串 |
| 空间复杂度 | O(m) | 递归深度最多为m，path最多存m个字符 |
| 输出空间 | O(4^m · m) | 需要存所有结果字符串 |
假设：
m = len(digits)（digits 的长度）- 每个数字最多对应 4 个字母（7 和 9）
为什么时间复杂度是这样：
- 第 1 位：最多 4 种选择
- 第 2 位：最多 4 种选择
- …
- 总组合数：
4 × 4 × … × 4 = 4^m- 每次存结果要
"".join(path)，长度是m👉 所以是
4^m × m
