LeetCode 题解工作台
组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件： 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = …
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们设计一个函数 $dfs(i, s)$，表示当前枚举到数字 ，还剩下和为 的数字需要枚举，当前搜索路径为 ，答案为 。 函数 $dfs(i, s)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 91 <= n <= 60
解题思路
方法一：剪枝 + 回溯（两种方式）
我们设计一个函数 ，表示当前枚举到数字 ，还剩下和为 的数字需要枚举，当前搜索路径为 ，答案为 。
函数 的执行逻辑如下：
方式一：
- 如果 ，且当前搜索路径 的长度为 ，说明找到了一组答案，将 加入 中，然后返回。
- 如果 或者 或者当前搜索路径 的长度大于 ，说明当前搜索路径不可能是答案，直接返回。
- 否则，我们可以选择将数字 加入搜索路径 中，然后继续搜索，即执行 ，搜索完成后，将 从搜索路径 中移除；我们也可以选择不将数字 加入搜索路径 中，直接执行 。
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def dfs(i: int, s: int):
if s == 0:
if len(t) == k:
ans.append(t[:])
return
if i > 9 or i > s or len(t) >= k:
return
t.append(i)
dfs(i + 1, s - i)
t.pop()
dfs(i + 1, s)
ans = []
t = []
dfs(1, n)
return ans
方式二：
- 如果 ，且当前搜索路径 的长度为 ，说明找到了一组答案，将 加入 中，然后返回。
- 如果 或者 或者当前搜索路径 的长度大于 ，说明当前搜索路径不可能是答案，直接返回。
- 否则，我们枚举下一个数字 ，即 ，将数字 加入搜索路径 中，然后继续搜索，即执行 ，搜索完成后，将 从搜索路径 中移除。
在主函数中，我们调用 ，即从数字 开始枚举，剩下和为 的数字需要枚举。搜索完成后，即可得到所有的答案。
时间复杂度 ，空间复杂度 。
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def dfs(i: int, s: int):
if s == 0:
if len(t) == k:
ans.append(t[:])
return
if i > 9 or i > s or len(t) >= k:
return
for j in range(i, 10):
t.append(j)
dfs(j + 1, s - j)
t.pop()
ans = []
t = []
dfs(1, n)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the pruning efficiency but is generally O(2^9) due to subset exploration. Space complexity is O(k) for the recursion stack and temporary combination storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to correctly implement pruning to avoid exploring impossible combinations.
- question_mark
Watch if recursion handles combination length and sum constraints precisely.
- question_mark
Check if candidates maintain uniqueness by incrementing the start number in recursion.
常见陷阱
外企场景- error
Failing to prune branches early, causing unnecessary computation.
- error
Not enforcing combination uniqueness, resulting in duplicate entries.
- error
Incorrectly handling base cases where k numbers are not yet reached but sum cannot match n.
进阶变体
外企场景- arrow_right_alt
Allowing repeated numbers in combinations, increasing possible branches.
- arrow_right_alt
Finding combinations for a dynamic range instead of 1-9.
- arrow_right_alt
Adding a target multiple sum, e.g., all combinations summing to multiples of n.