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


  • 0
    R
    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.


  • 0
    B

    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).


  • 0
    R

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


  • 0
    R

    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 !!!!


Log in to reply
 

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