<p>Given two integers <code>n</code> and <code>k</code>, return <em>all possible combinations of</em> <code>k</code> <em>numbers chosen from the range</em> <code>[1, n]</code>.</p>

<p>You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 4, k = 2
<strong>Output:</strong> [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
<strong>Explanation:</strong> There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1, k = 1
<strong>Output:</strong> [[1]]
<strong>Explanation:</strong> There is 1 choose 1 = 1 total combination.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 20</code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
</ul>

#pragma GCC target("avx, mmx, sse2, sse3, sse4")

auto disableSync = [](void) noexcept -> int
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

class Solution final
{
private:
    int n;
    std::vector<std::vector<int>> combinations;

public:
    std::vector<std::vector<int>> combine(const int n, const int k) noexcept
    {
        this->n = n;
        const std::array<size_t, 21> factorials = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
                                                   39916800,  479001600, 6227020800, 87178291200, 1307674368000,
                                                   20922789888000, 355687428096000, 6402373705728000,
                                                   121645100408832000, 2432902008176640000};
        this->combinations.reserve(factorials[n] / (factorials[k] * factorials[n - k]));
        std::vector<int> combination;
        combination.reserve(k);
        this->setCombinations(1, k, combination);
        return this->combinations;
    }

private:
    void setCombinations(const int start, const int k, std::vector<int> combination) noexcept
    {
        if (k == 0)
        {
            this->combinations.push_back(combination);
            return;
        }
        const int end = this->n - k + 1;
        for (int i = start; i <= end; ++i)
        {
            combination.push_back(i);
            this->setCombinations(i + 1, k - 1, combination);
            combination.pop_back();
        }
    }
};
120737