Let `C(n,k)`

be the number of combinations to choose `k`

elements out of `n`

elements. Then there are only two cases:

- element
`n`

is chosen: so we only need to choose`k-1`

out of first`n-1`

and there are`C(n-1,k-1)`

combinations. - element
`n`

is not chosen: so we need to choose`k`

out of first`n-1`

and there are`C(n-1,k)`

combinations.

So we have equality`C(n,k) = C(n-1,k-1)+C(n-1,k)`

.

```
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
if (k == 1) { // base case
for (int i = 1; i <= n; ++i) res.push_back({i});
return res;
}
else if (k == n) { // base case
res.resize(1);
for (int i = 1; i <= n; ++i) res[0].push_back(i);
return res;
}
res = combine(n-1,k); // all combinations without n
auto tmp = combine(n-1,k-1);
for (auto& x:tmp) x.push_back(n); // all combinations with n
res.insert(res.end(), tmp.begin(), tmp.end());
return res;
}
```