### LeetCode 组合总和 III 的 Python 实现 组合总和 III 的问题要求从 1 到 9 的数字中选出 `k` 个数，使它们的和为 `n`。以下是一个优雅的 Python 实现方案，使用了标准库 `itertools` 中的 `combinations` 方法来生成所有可能的组合，并筛选出满足条件的结果[^1]。 ```python from itertools import combinations class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: return [item for item in list(combinations(range(1, 10), k)) if sum(item) == n] ``` #### 解决方案分析 上述代码的核心思想是利用 `itertools.combinations` 函数生成从 `range(1, 10)` 中选取 `k` 个元素的所有组合，并通过列表推导式过滤出那些组合中元素之和等于 `n` 的结果[^1]。这种方法简洁高效，避免了手动递归或回溯实现的复杂性。 #### 时间与空间复杂度 - **时间复杂度**：由于 `combinations` 会生成所有可能的组合，其复杂度为 \(O(C(9, k))\)，其中 \(C(9, k)\) 表示从 9 个数字中选择 `k` 个的组合数。此外，还需要对每个组合计算其和，因此总体复杂度为 \(O(C(9, k) \times k)\)。 - **空间复杂度**：主要由存储所有符合条件的组合决定，最坏情况下为 \(O(C(9, k))\)[^1]。 --- ### 使用回溯法的解决方案 除了使用 `itertools.combinations`，还可以通过回溯法（Backtracking）来解决问题。以下是基于回溯法的实现[^3]： ```python class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: result = [] def backtrack(start, path, remaining_sum): # 如果路径长度等于 k 且剩余和为 0，则找到一个解 if len(path) == k and remaining_sum == 0: result.append(path.copy()) return # 如果路径长度超过 k 或剩余和小于 0，提前终止 if len(path) > k or remaining_sum < 0: return # 遍历从 start 开始的数字 for i in range(start, 10): path.append(i) backtrack(i + 1, path, remaining_sum - i) path.pop() # 回溯 backtrack(1, [], n) return result ``` #### 解决方案分析 该方法通过递归和回溯逐步构建符合条件的组合。在每次递归调用中，尝试将当前数字加入路径，并递归地处理剩余的数字和目标和。如果路径长度达到 `k` 且剩余和为 0，则将当前路径加入结果列表[^3]。 #### 时间与空间复杂度 - **时间复杂度**：类似于第一种方法，取决于生成的组合数量，最坏情况下为 \(O(C(9, k) \times k)\)。 - **空间复杂度**：递归栈的深度最多为 `k`，因此空间复杂度为 \(O(k)\)。 --- ### 示例运行 #### 输入 ```python k = 3 n = 7 ``` #### 输出 ```python [[1, 2, 4]] ``` #### 输入 ```python k = 3 n = 9 ``` #### 输出 ```python [[1, 2, 6], [1, 3, 5], [2, 3, 4]] ``` ---