Combination Sum III

216. 组合总和III

分析

采用深度优先搜索（DFS）+ 回溯来解决问题：

递归函数设计：
- 参数：
  - 当前搜索起点 start（避免重复选择数字）
  - 当前目标和 n
  - 当前还需要选的数字个数 k
- 终止条件：
  - 如果 n == 0 且 k == 0 ，说明找到了一组符合条件的组合，将其加入结果列表
  - 如果 n != 0 且 k == 0 ，或者 n < 0 ，直接返回（剪枝）
递归遍历：
- 从 start 开始，依次尝试数字 i （范围 start 到 9
- 每次选择 i 后递归：将 i 加入路径，更新 n = n - i ，更新 k = k - 1
- 递归返回后撤销选择 i（回溯）
剪枝优化：
- 如果 i > n ，则跳过剩余数字，直接剪枝，因为后续数字只会更大

时间复杂度

最多有 9 / k 个组合，其中 n / k = n! / k!(n-k)!
每次递归需要 O(k) 的时间来复制路径

总时间复杂度为 O(k * 9 / k)

空间复杂度

路径 path 的最大深度为 k ，递归调用栈的深度也为 k

空间复杂度为 O(k)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution
{
public:
    std::vector<std::vector<int>> res; // 存储结果
    std::vector<int> path;             // 当前路径

    vector<vector<int>> combinationSum3(int k, int n)
    {
        dfs(1, n, k); // 从数字1开始搜索
        return res;
    }

    void dfs(int start, int n, int k)
    {
        if (n == 0)
        {
            if (k == 0)
                res.push_back(path); // 找到一个合法组合
            return;
        }
        if (k == 0) return; // 数字用完，但和未达到目标

        for (int i = start; i <= 9; ++i)
        {
            if (i > n) break; // 剪枝：当前数字大于目标和
            path.push_back(i); // 选择数字i
            dfs(i + 1, n - i, k - 1); // 递归搜索
            path.pop_back(); // 回溯，撤销选择
        }
    }
};