77. 组合

每个点选或不选

得到第一种写法，效率比较低

class Solution {
public:
    // 1~n 选k个
    int n, k;
    vector<vector<int>> res;
    vector<bool> b;
    vector<vector<int>> combine(int n_, int k_) {
        n = n_, k = k_;
        b.resize(n);
        dfs(0, k);
        return res;
    }

    // 到了下标u
    void dfs(int u, int k)
    {
        // 结束
        if (u == n)
        {
            int cnt = 0;
            for (int i = 0; i < n; i ++)
                if (b[i])
                    cnt ++;
            if (cnt == k)
            {
                vector<int> tmp;
                for (int i = 0; i < n; i ++)
                    if (b[i])
                        tmp.push_back(i + 1);
                res.push_back(tmp);
            }
            return;
        }
        b[u] = true;
        dfs(u + 1, k);
        b[u] = false;
        dfs(u + 1, k);
    }
};

其实不需要开bool数组然后遍历到叶子节点，用一个全局tmp数组记录答案即可，dfs时传入下标