LeetCode 77グループHERODINGのLeetCodeの道
2つの整数nおよびkが与えられ、1...nのすべての可能なk個の数の組合せが返される.
例:
入力:n=4,k=2出力:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]
解題の構想:またよく知っているdfsを使ってこの問題を解決して、もちろん枝を切ります.各数について、2つの可能性しかなく、選択するか、選択しないか、選択すると長さがKに達すると終了し、直接return、長さがKに足りない直接return、これは剪定の過程であり、コードは以下の通りである.
例:
入力:n=4,k=2出力:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]
解題の構想:またよく知っているdfsを使ってこの問題を解決して、もちろん枝を切ります.各数について、2つの可能性しかなく、選択するか、選択しないか、選択すると長さがKに達すると終了し、直接return、長さがKに足りない直接return、これは剪定の過程であり、コードは以下の通りである.
class Solution {
public:
vector<int> temp;
vector<vector<int>> ans;
void dfs(int cur, int n, int k) {
// ：temp [cur, n] k， k temp
if (temp.size() + (n - cur + 1) < k) {
return;
}
//
if (temp.size() == k) {
ans.push_back(temp);
return;
}
//
temp.push_back(cur);
dfs(cur + 1, n, k);
temp.pop_back();
//
dfs(cur + 1, n, k);
}
vector<vector<int>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
};