# [77\. Combinations](https://leetcode.com/problems/combinations/)

:::spoiler Solution

class Solution {
private:
    vector<vector<int>> res;
    vector<int> comb;
public:
    vector<vector<int>> combine(int n, int k)
    {
        backtracking(n, k, 1);
        return res;
    }
    
    void backtracking(int n, int k, int start)
    {
        if (comb.size() == k) res.push_back(comb);
        if (comb.size() > k) return;
        for (int i = start; i <= n; ++i)
        {
            comb.push_back(i);
            backtracking(n, k, i + 1);
            comb.pop_back();
        }
    }
};

- T: $O\left(n! \over k!(n - k)!\right)$
- S: $O(k)$, where `k` is the combination numbers.
:::