<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>

struct Combination {
    int n;
    int k;
    list<int> combination;

    Combination(int n, int k) : n(n), k(k) {
        for(int i=1; i<=k; i++) {
            combination.push_back(i);
        }
    }

    vector<int> getCombination() {
        return vector<int>(combination.begin(), combination.end());
    }

    bool canIncrement() {
        int expectedValue = n;
        for(auto revIt = combination.rbegin(); revIt != combination.rend(); revIt++) {
            if(*revIt < expectedValue--) {
                return true;
            }
        }
        return false;
    }

    bool increment() {
        if(!canIncrement()) {
            return false;
        }

        int firstValue = combination.front();
        int maxValue = n;
        while(combination.size()) {
            if(++combination.back() <= maxValue--) {
                break;
            } else {
                combination.pop_back();
            }
        }

        if(combination.empty()) {
            combination.push_back(++firstValue);
        }
        while(combination.size() != k) {
            combination.push_back(combination.back() + 1);
        }
        return true;
    } 
};

class Solution {

public:
    vector<vector<int>> combine(int n, int k) {
        Combination combination(n, k);
        vector<vector<int>> result;
        do {
            result.push_back(combination.getCombination());
        } while (combination.increment());
        return result;
    }
};

// set of numbers [1, n]
// k chosen numbers
// n choose k -> n!/k!(n-k)!
// choosing a number from a from [1,n], the next number chosen can be from [1,n] - a, and so on
// choose number from 1->n (actually [1, n-k+ithSelection]), increase ithSelection from [1, k]
// append to existing selection and add to output
64712