LeetCode 0077 - Combinations
# Hints
- DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given two integers and , return all possible combinations of numbers out of 1 ... n
.
You may return the answer in any order .
Example 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Constraints:
# 题意
给定两个正整数 和 ,求集合 的所有大小为 的子集。
# 题解
水题,直接 DFS 枚举所有方案即可。可以做点简单的剪枝提高效率。
# AC代码
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
// DFS
vector<vector<int>> res;
vector<int> vec;
dfs(1, vec, res, n, k);
// 返回
return res;
}
// 深度优先搜索
void dfs(int depth, vector<int> & vec, vector<vector<int>> & res, const int n, const int k) {
// 递归终止
if (vec.size() == k) {
res.push_back(vec);
return;
}
if (depth == n + 1) {
return;
}
// 剪枝
if (n - depth < k - (vec.size() + 1)) {
return;
}
// 递归
vec.push_back(depth);
dfs(depth + 1, vec, res, n, k);
vec.pop_back();
dfs(depth + 1, vec, res, n, k);
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01