29 lines
789 B
C++
29 lines
789 B
C++
#include "s0077_combinations.hpp"
|
|
|
|
void combineDFS(int n, int k, int begin, vector<int> &path,
|
|
vector<vector<int>> &result) {
|
|
// 当 path 长度等于 k 时停止迭代，并将加入结果
|
|
if (path.size() == k) {
|
|
result.push_back(path);
|
|
return;
|
|
}
|
|
|
|
// 遍历可能的搜索起点
|
|
// 在这一步中，每一次循环都可以对末尾进行限制来剪枝
|
|
for (int i = begin; i <= n - (k - path.size()) + 1; ++i) {
|
|
// 将 i 加入路径
|
|
path.push_back(i);
|
|
// 下一轮搜索
|
|
combineDFS(n, k, i + 1, path, result);
|
|
// 回溯，撤销处理的节点
|
|
path.pop_back();
|
|
}
|
|
}
|
|
|
|
vector<vector<int>> S0077::combine(int n, int k) {
|
|
vector<vector<int>> result;
|
|
vector<int> path;
|
|
combineDFS(n, k, 1, path, result);
|
|
return result;
|
|
}
|