216. 组合总和 III - Combination Sum III

🎯 问题描述（来源于LeetCode）

描述：
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 到 9 的正整数，且每个组合中的数字不能重复使用（每个数字最多用一次）。
返回所有可能的有效组合的列表。答案可以按任意顺序返回。

说明：

组合中的数字不要求顺序（即 [1,2,3] 和 [3,2,1] 被视为同一组合）。
数字范围固定为 1...9。

示例：

示例 1：

1 2	输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2：

1 2	输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

示例 3：

1 2	输入: k = 4, n = 1 输出: []

💻 解题思路

思路：回溯法（逆序枚举 + 剪枝）

算法步骤

初始化结果列表 ans 和当前路径列表 path。
定义递归函数 dfs(i, target)，其中 i 表示当前可选的数字上限（从 i 向下选择），target 表示剩余需要凑的和：
- 计算还需选的数字个数 d = k - len(path)。
- 如果 d == 0 and target == 0，说明已选满 k 个数且和恰好为 n，将 path 的副本加入 ans 并返回。
- 如果 i == 0 或 d < 0 或 target < 0，则返回（无效状态）。
- 否则，尝试两个分支：
  - 不选数字 i：递归 dfs(i-1, target)。
  - 选数字 i：将 i 加入 path，递归 dfs(i-1, target - i)，然后回溯弹出 i。
从 dfs(9, n) 开始搜索（因为最大数字为 9）。
返回 ans。

代码实现

from typing import List

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        path = []
        
        def dfs(i, target):
            d = k - len(path)
            if d == 0 and target == 0:
                ans.append(path[:])
                return
            if i == 0 or d < 0 or target < 0:
                return
            # 不选 i
            dfs(i-1, target)
            # 选 i
            path.append(i)
            dfs(i-1, target - i)
            path.pop()
        
        dfs(9, n)
        return ans

📊 性能分析

时间复杂度： $O(C(9, k) \cdot k)$ ，最坏情况枚举所有组合数，每个组合复制需要 $O(k)$ 时间。
空间复杂度： $O(k)$ ，递归栈深度和路径存储。

思考

该解法采用逆序枚举（从 9 向下递归），通过参数 d 和 target 进行剪枝。关键点在于：

当剩余需要选的数字个数 d 大于当前可选的数字范围 i 时，实际上递归会自然终止（因为 i 不断减小，最终 i < d 导致无法选满），但代码中未显式利用 i >= d 剪枝，而是依靠 i == 0 和 d < 0 来停止。
分支顺序为先不选再选，保证了所有组合都会被枚举，且不会重复（因为每个数字只能选一次，且按递减顺序选择，避免了顺序不同导致的重复）。
由于数字范围固定为 1-9，搜索空间有限，此方法效率很高。

优点：