Solved with **Backtracking** that looks a lot like N-Queen, Subsets and Permutations.

A little tweak on the parameter k since Choosing k numbers from n is sort of equivalent to

choosing n-k numbers from n numbers. Can be a lot faster in cases where k is very close to n. Say n = 20, k = 18. We actually just need to pick out 2 numbers.

'''

```
def combine(self, n, k):
_k = k
if k > n / 2 + 1:
k = n - k
ret = []
self.dfs(n, k, [], ret)
if _k != k:
temp = []
for i in ret:
temp.append([j for j in range(1, n + 1) if j not in i])
return temp
return ret
def dfs(self, n, k, cur, ret):
if len(cur) == k:
ret.append(cur[::])
return
temp = 0 if not cur else cur[-1]
for i in range(1+temp, n+1):
cur.append(i)
self.dfs(n, k, cur, ret)
cur.pop()
```

'''