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

class Solution {
public:
/*
    int factorial(int number) {
        int results = 1;
        while (number != 0) {
            results *= number;
            number--;
        }
        return results;
    }
/*
    static bool vec_compare(const vector<int>& first, const vector<int>& second) {
        return first.size() > second.size();
    }
    void addNumber(int max_size, int current_number, int to_be_added, vector<vector<int>>& res) {
        if (current_number == 0)
            return;
        // sort the results vector
        sort(res.begin(), res.end(), vec_compare);
        // loop through the results vector
        int curr_to_be_added = to_be_added;
        for (int i=0; i<res.size(); i++) {
            // if current vector is full, move to the next one
            if (res[i].size() == max_size)
                continue;
            if (curr_to_be_added == 0)
                break;
            res[i].push_back(current_number);
            curr_to_be_added--;
        }
        current_number--;
        addNumber(max_size, current_number, to_be_added, res);
        return;
    }

    vector<vector<int>> combine(int n, int k) {
        // need to create some kind of loop, not dependent on k
        // if n == k, no loop needed, add all numbers to 1 vector
        // if k == 1, loop needed, but only once
        // if k == 2, need an outside loop that 

        // 3,4
        // 1,4
        // 1,2
        // 2,3
        // 2,4
        // 1,3

        // 12
        // 23
        // 34
        // 41
        // 12
        // 23

        // try recursion
        // need to know max, which is k
        // need to know the number of combinations in which 1 number will be included
        int number_of_combos_total = factorial(n)/(factorial(k)*factorial(n-k));
        int num_comb_ind = factorial(n-1)/(factorial(k-1)*factorial(n-k));
        cout<<number_of_combos_total<<endl;
        cout<<num_comb_ind<<endl;



        vector<vector<int>> res(number_of_combos_total, vector<int>(0));


        // recursive call
        addNumber(k,n,num_comb_ind,res);

        return res;

    }

    vector<vector<int>> combine(int n, int k) {
        // get the number of combos that will be returned
        int combos = factorial(n)/(factorial(k)*factorial(n-k));

        vector<vector<int>> res(combos,vector<int>(0));

        // initialize each vector
        for (int i=0; i<res.size(); i++) {
            for (int j=1; j<=n; j++) {
                res[i].push_back(j);
            }
        }

        // delete from each combo
        vector<int>::iterator vec;
        while (res[res.size()-1].size() != k) {
            int index = 0;
            int curr_size = res[0].size();
            for (int i=0; i<res.size(); i++) {
                vec = res[i].begin();
                res[i].erase(vec+index);
                index++;
                index %= curr_size;
            }
        }

        return res;
    }
    */

    void chooseVec(int num, int n, int k, vector<int> curr_vec, vector<vector<int>>& res) {
        int remaining = k-curr_vec.size();
        if (remaining > n-num+1)
            return;
        // add current number to curr_vec
        curr_vec.push_back(num);
        // base case: vec is full, add it to the res and return
        if (curr_vec.size() == k) {
            res.push_back(curr_vec);
            return;
        }
        // otherwise, make calls to chooseVec again with increasing num
        for (int i=num+1; i<=n; i++) {
            chooseVec(i, n, k, curr_vec, res);
        }
        return;
    }

    vector<vector<int>> combine(int n, int k) {
        // call recursive function
        vector<vector<int>> res;
        vector<int> curr_vec;
        for (int i=1; i<=n-k+1; i++) {
            chooseVec(i, n, k, curr_vec, res);
        }
        return res;
    }
};
137337