题目描述
给定数字1到9，从中选 $k$ 个数，不考虑顺序，使得它们的和等于 $n$，返回所有方案。要求方案中不包含相同数字，且答案中不包含相同的方案。
样例1
输入：k = 3, n = 7
输出：[[1,2,4]]
样例2
输入：k = 3, n = 9
输出：[[1,2,6], [1,3,5], [2,3,4]]
算法
(DFS) $O(C_9^k \times k)$
暴力搜索出所有从9个数中选 $k$ 个的方案，记录所有和等于 $n$ 的方案。
为了避免重复计数，比如 {1, 2, 3} 和 {1, 3, 2} 是同一个集合，我们对集合中的数定序，每次枚举时，要保证同一方案中的数严格递增，即如果上一个选的数是 $x$，那我们从 $x+1$ 开始枚举当前数。
时间复杂度分析：从9个数中选 $k$ 个总共有 $C_9^k$ 个方案，将每个方案记录下来需要 $O(k)$ 的时间，所以时间复杂度是 $O(C_9^k \times k)$。
C++ 代码
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k, n, 1);
return ans;
}
void dfs(int k, int n, int start)
{
if (!k)
{
if (!n) ans.push_back(path);
return;
}
for (int i = start; i <= 10 - k; i ++ )
if (n >= i)
{
path.push_back(i);
dfs(k - 1, n - i, i + 1);
path.pop_back();
}
}
};
没太理解y总的代码，但是根据之前讲过的combinations， 77题，写的这个代码，也可以过
我直接用了i <= 9, 没理解
i <= 10 - ki <= 10 - k是怎么得出来的没搞明白，麻烦点播一下如果
i > 10 - k，那么当前方案无论如何都无法选够k个数了。y总，看了你的评论，还是没懂
i <= 10 - k的缘由，能再解释一下吗hh。还是不太懂
$k$ 是还需要几个数，从 $10 − k + 1$ 开始到 $9$ 只有 $k−1$ 个数
对滴。
确认时间复杂度的分析是对的么？
现在改成 $C_9^k \times k$ 了，你觉得对不
我说说我的想法：
我觉得不应该这么描述吧，因为这个组合公式代表的是方案的数量，并不代表代码执行的时间复杂度。
大O描述的含义是：随着输入规模的增加，代码执行时间增长的速度（或规模），是从CC189上看到的。
从下面我的代码可以看出，如果不考虑减枝的话，那么时间复杂度是O(2^n)， 即 O(2^9)。
因为n是9，即2^9是个常数，那么时间复杂度应该是O(1)。
如果要是考虑k的话，其实我并不确定怎么去描述事件复杂度，但我觉得应该不会是 Ck9×k
这里的时间复杂度就是指代码的计算量级，它是由代码决定的，相同算法不同的代码实现方式，时间复杂度可能是不同的。一般的搜索树的最后一层节点数量和整个搜索树的节点数的数量级是相同的，而我写的代码里搜索树的最后一层节点数量就是方案数量，因此总共的dfs执行次数和方案数是相同级别的，然后每个dfs中的计算量最多是 $O(k)$，因此总时间复杂度就是 $O(方案数 \times k)$。
这种题感觉已经理不清楚了。有没有什么规律之类的？
求组合数一般要记个起始下标，求排列数一般每次从头开始枚举。
👍