力扣(leetcode)77.组合——深搜(DFS)

4902 ワード

力扣(leetcode)77.组合——深搜(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;
    }
};