<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:
    void f(int ind, int n, int k, vector<int> curset, vector<vector<int>> &res){
        //a
        if(k==0){
            res.push_back(curset);
            return;
        }
        //b
        if(ind>n){
            return;
        }
        //c
        //pruning - when k=3 and n=2 means when slots(k) are more than no. child(n) --> return 
        if(n-ind+1<k){
            return;
        }
        //d
        int i; 
        for(i=ind; i<=n;i++){
            curset.push_back(i);
            f(i+1, n, k-1, curset, res);
            curset.pop_back();
        }
        /* n=4 k=2 */
        

    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        f(1,n,k,{}, res);
        return res;
    }
};
/*
f(i=1,k=2,{}) {
    a X
    b X
    c f(i=2,k=2,{}) {
        a X
        b X
        c f(i=3,k=2,{}) {
            a X
            b X
            c f(i=4,k=2,{}) {
                a X
                b X
                c f(i=5,k=2,{}) {
                    a X
                    b Y -> return
                }
                d f(i=5,k=1,{4}) {
                    a X
                    b Y -> return
                }
            }
            d f(i=4,k=1,{3}) {
                a X
                b X
                c f(i=5,k=1,{3}) {
                    a X
                    b Y ->return
                }
                d f(i=5,k=0,{3,4}) {
                    a Y -> push{3,4}, return
                }
            }
        }
        d f(i=3,k=1,{2}) {
            a X
            b X
            c f(i=4,k=1,{2}) {
                a X
                b X
                c f(i=5,k=1,{2}) {
                    a X
                    b Y -> return
                }
                d f(i=5,k=0,{2,4}) {
                    a Y -> push{2,4}, return
                }
            }
            d f(i=4,k=0,{2,3}) {
                a Y -> push{2,3}, return
            }
        }
    }
}
n=3 k=2
f(i=1,k=2,{}){
    a X
    b x
    c f (i=2, k=2, {}){
        a x
        b x
        c f(i=3, k=2, {}){
            a x
            b x 
            c f(i=4, k=2, {}){
                a x
                b --> RETURN
            }  
            d f(i=4, k=1, {3}){
                a x
                b --> RETURN
            }
        }
        d f(i=3, k=1, {2}){
            a x
            b x
            c f(i=4, k=1, {2}){
                a x
                b --> RETURN
            }
            d f(i=4, k=0, {2,3}){
                a --> RETURN and push
            }
        }
        
    }
}














































*/

118662