0.引言
1.理论基础
77.# 组合
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (77.26%) | 1323 | - |
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 201 <= k <= n
回溯
起始本质都是递归都是深搜
/*
* @lc app=leetcode.cn id=77 lang=cpp
*
* [77] 组合
*/
// @lc code=start
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
std::vector<int> one_combine;
std::vector<std::vector<int>> res;
dfs(n, k, one_combine, res, 1);
return res;
}
private:
void dfs(int n, int k, std::vector<int>& one_combine,
std::vector<std::vector<int>>& res, int start_idx) {
if (one_combine.size() == k) {
res.push_back(one_combine);
return;
}
for (int i = start_idx; i <= n; ++i) {
one_combine.push_back(i);
dfs(n, k, one_combine, res, i + 1); // i 为隐式回溯
one_combine.pop_back();
}
}
};
// @lc code=end
剪枝
挖坑
