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

"""
Let's try n = 4, k = 2

(n, k) 
-> (n - 1, k)
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
-> (n - 1, k - 1) + insert "n" into every combination
[[1, 5], [2, 5], [3, 5], [4, 5]]

n = 1, k = 1

n = 2, k = 2
(1, 2) ==> []

(1, 1) ==> [[1]]

[[1, 2]]

n = 2, k = 1

(1, 1) ==> [[1]]

(1, 0) ==> [ [] ], [[2]]

if k = 0, we should return a single empty list [ [] ]


"""

class Solution:
    def __init__(self):
        self.mem = {}

    def combine(self, n: int, k: int) -> List[List[int]]:
        # Base Cases
        if (n, k) in self.mem:
            return self.mem[(n, k)]
        if k == 0:
            self.mem[(n, k)] = [[]]
            return [[]]
        if k > n:
            self.mem[(n, k)] = []
            return []
        if n == 1:
            self.mem[(n, k)] = [[1]]
            return [[1]]
        
        combs1 = self.combine(n - 1, k)
        new_combs = combs1.copy()

        combs2 = self.combine(n - 1, k - 1)
        for comb in combs2:
            new_combs.append(comb + [n])
        
        # print("n = {}, k = {}, comb1 = {}, comb2 = {} result = {}".format(n, k, combs1, combs2, result))

        self.mem[(n, k)] = new_combs
        return new_combs


72908