```
class Solution(object):
def sol(self, begin, n, k):
if k == 0:
return [[]]
if n - begin + 1 == k:
return [[i for i in xrange(begin, n + 1)]]
# include begin
x = self.sol(begin + 1, n, k - 1)
for i in x:
i.append(begin)
# not including begin
y = self.sol(begin + 1, n, k)
return x + y
def combine(self, n, k):
return self.sol(1, n, k)
```