77. Combinations

backtracking O(k*C(n, k)) time O(C(n, k)) space
这里时间要乘k是因为最后写到res里需要k步

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(1, k, n);
        return res;
    }

    void dfs(int b, int k, int n) {
        if (v.size() == k) {
            res.push_back(v);
            return;
        }
        for (int i = b; i <= n && v.size() + n - i + 1 >= k; ++i) { // 第二个终止条件是一个优化 表示剩余的数加到v里也不够k个则不再往下做了 可有可无 （当前是i之前已经查看了i -1个数放了v.size()个数 所以是v.size() + n - (i - 1)要至少为k）
            v.push_back(i);
            dfs(i + 1, k, n);
            v.pop_back();
        }
    }

    vector<int> v;
    vector<vector<int>> res;
};

iterative

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        if (n <= 0 || k <= 0) return {};
        vector<vector<int>> res;
        for (int i = 1; i <= n; ++i) {
            res.push_back({i});
        }
        for (int i = 2; i <= k; ++i) {
            vector<vector<int>> t;
            for (int j = 1; j <= n; ++j) {
                for (const auto &v : res) {
                    if (v.back() >= j) break;
                    t.push_back(v);
                    t.back().push_back(j);
                }
            }
            t.swap(res);
        }
        return res;
    }
};