# C++ recursive solution inspired by combination equation C(n,k) = C(n-1,k-1)+C(n-1,k) detail explanation

• 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.