28 lines
726 B
C++
28 lines
726 B
C++
#include "s0216_combination_sum_iii.hpp"
|
|
|
|
void combinationSum3DFS(int k, int n, int begin, vector<int> &path, int sum,
|
|
vector<vector<int>> &result) {
|
|
// 终止条件：高度达到上限且总和为 n
|
|
if (path.size() == k && sum == n) {
|
|
result.push_back(path);
|
|
return;
|
|
}
|
|
|
|
// 开始迭代
|
|
// 当总和 > n 时，剪枝
|
|
for (int i = begin; i <= 9 && sum + i <= n; ++i) {
|
|
sum += i;
|
|
path.push_back(i);
|
|
combinationSum3DFS(k, n, i + 1, path, sum, result);
|
|
sum -= i;
|
|
path.pop_back();
|
|
}
|
|
}
|
|
|
|
vector<vector<int>> S0216::combinationSum3(int k, int n) {
|
|
vector<int> path{};
|
|
vector<vector<int>> result;
|
|
combinationSum3DFS(k, n, 1, path, 0, result);
|
|
return result;
|
|
}
|