combinations.cpp

// Time:  O(k * C(n, k))
// Space: O(k)

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        static const auto& add_result =
            [](const auto& nums, const auto& idxs, auto *result) {
                result->emplace_back();
                transform(cbegin(idxs), cend(idxs), back_inserter(result->back()),
                          [&nums](const auto& i) {
                              return nums[i];
                          });
            };
        static const auto& next_pos =
            [](const auto& n, const auto& k, const auto& idxs) {
                int i = k - 1;
                for (; i >= 0; --i) {
                    if (idxs[i] != i + n - k) {
                        break;
                    }
                }
                return i;
            };

        if (k > n) {
            return {};
        }
        vector<int> nums(n), idxs(k);
        iota(begin(nums), end(nums), 1), iota(begin(idxs), end(idxs), 0);
        vector<vector<int>> result;
        add_result(nums, idxs, &result);
        for (int i; (i = next_pos(n, k, idxs)) >= 0;) {
            ++idxs[i];
            for (int j = i + 1; j < k; ++j) {
                idxs[j] = idxs[j - 1] + 1;
            }
            add_result(nums, idxs, &result);
        }
        return result;
    }
};

// Time:  O(n!)
// Space: O(n)
class Solution2 {
    public:
        void dfs(int n, int k, int start, vector<int> &path, vector<vector<int> > &ans) {
            if(k == 0) {
                ans.push_back(path);
                return;
            }

            for(int i = start; i <= n; ++i) {
                path.push_back(i);
                dfs(n, k - 1, i + 1, path, ans);
                path.pop_back();
            }
        }
        vector<vector<int> > combine(int n, int k) {
            vector<vector<int> > ans;
            vector<int> path;
            dfs(n, k, 1, path, ans);
            return ans;
        }
};