Perhaps the simplest solution using recursion(backtracing).

• The idea is that C(n,k) = C(n-1, k-1) U n + C(n-1,k), do you get this?

``````class Solution {
public:
vector<vector<int> > combine(int n, int k) {

vector<vector<int> > result;
if (n < 1 || k <1 || k > n)
{
return result;
}

result = combine(n-1, k-1);

if(result.empty())
{
result.push_back(vector<int>{n});
}
else
{
for (vector<vector<int> >::iterator it = result.begin();
it!= result.end(); it++)
{
it->push_back(n);
}
}
vector<vector<int> > result2 = combine(n-1, k);
result. insert(result.end(), result2.begin(), result2.end());

return result;
}
};``````

• I don't want to copy the returned vectors every time, so I just flip coins:

``````class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
if (n < 1 || k < 1 || k > n) return result;
vector<int> v;
collect(n, k, 0, v, result);
return result;
}
void collect(int n, int k, int i, vector<int> &v, vector<vector<int>> &ret) {
if (v.size() == k) {
ret.push_back(v);
return;
}
while (i < n) {
v.push_back(i + 1);
collect(n, k, i + 1, v, ret);
v.pop_back();
i++;
}
}
};
``````

• really quite simple

• That's indeed the DP solution. Very nice.

• "C(n,k) = C(n, 1) * C(n-1, k-1)" doesn't look right to me. I think it should be C(n,k) = C(n, 1) / k * C(n-1, k-1). The code is neat though, thx :-)

• Thanks, you are right. I've edited my answer. :)

• Can you explain your approach in detail ?

Especially this part of code -

``````if(result.empty())
{
result.push_back(vector<int>{n});
}
else
{
for (vector<vector<int> >::iterator it = result.begin();
it!= result.end(); it++)
{
it->push_back(n);
}
}``````

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