力扣(leetcode)77.组合——深搜(DFS)
4902 ワード
力扣(leetcode)77.组合——深搜(DFS)
原題転送ゲート問題解:配列組合せ+dfs:n個の異なる数字の中からk個の異なる数字を探し出して、全部でC(n,k)の中の情況があります;この問題は全配列が必要で、深さ優先検索(dfs)でできます.コードをつけます.
原題転送ゲート問題解:配列組合せ+dfs:n個の異なる数字の中からk個の異なる数字を探し出して、全部でC(n,k)の中の情況があります;この問題は全配列が必要で、深さ優先検索(dfs)でできます.コードをつけます.
class Solution {
public:
int n,k;
vector <vector <int>>ans;
vector <int>s;
void dfs(int x, int y) {//x: s ,y: 。
s.push_back(x);
if (y == k) {
ans.push_back(s);
s.pop_back();
return;
}
for (int i = x + 1; i <=n; i++) {
dfs(i, y + 1);
}
s.pop_back();// 。
}
vector<vector<int>> combine(int a, int b) {
n=a;
k=b;
for (int i = 1; i <= n; i++) {
dfs(i, 1);
}
return ans;
}
};