# I want to know the time complexity of this code, could you help me？

• ``````class Solution {
public:
vector<vector<int> > ans;
vector<int> cur;
int n_, k_;
vector<vector<int> > combine(int n, int k) {
cur.clear(), ans.clear();
n_=n, k_=k;
dfs(1,0);
return ans;
}
void dfs(int ni, int ki)
{
if(ki==k_)
{
ans.push_back(cur);
return ;
}
if(ni>n_) return ;
dfs(ni+1, ki);
cur.push_back(ni);
dfs(ni+1, ki+1);
cur.pop_back();
}
};
``````

seems C(n,k), but not sure, upper bound is 2^n exactly.

But the proning is not clear.

Could anybody help me? Thanks.

• This seems C(n, k) (not exponential) as I mentioned in the previous reply. If you re-write the code so that you go back from n, k to 1, 0 (instead of going forward), then the recurrence formula would look like:

T(n, k) = T(n-1, k) + T(n-1, k-1)

Which is the same as C(n, k).

• don't consider about the pruning? Many people say that time is C(n,k), but I am not sure

• Cool!! This is a very good explanation, code going forward, but analysis backward, and backward can easily get recusive equation, and this a classical combination equation. Thanks !!!!

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