C++ concise recursive solution C(n,k) ->C(n-1,k-1) / 8ms


  • 13
    S
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> ans;
            vector<int> temp;
            combine(1,n,k,ans,temp); //call fuction to get combination of k numbers which range is 1-n
            return ans;
        }
    private:
           void combine(int begin,int n, int k, vector<vector<int>> &ans, vector<int>& temp){
                if(k==0){ 
                    ans.push_back(temp);
                    return;
                } 
                //condition : n-i+1 is the range, range must greater than k
                for(int i=begin;n-i+1>=k;i++){ // for the ith iteration, get the combination of i and k-1 numbers differ from i.
                    temp.push_back(i); 
                    combine(i+1,n,k-1,ans,temp);// get the combination of k-1 numbers which range is(i+1,n) 
                    temp.pop_back();
                }
            }
    };

  • 0
    G
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            if (n < 1 || k < 1 || k > n) {
                return vector<vector<int>>();
            }
            vector<vector<int>> res;
            vector<int> tmp;
            combine(n, k, res, tmp);
            return res;
        }
        
        void combine(int start, int k, vector<vector<int>>& res, vector<int>& tmp) {
            if (k == 0) {
                res.push_back(tmp);
                return;
            }
    
            for (int i=start; i >= k; i--) {
                tmp.push_back(i);         
                combine(start-1, k-1, res, tmp);
                tmp.pop_back();
            }
        }
    };
    

    Why this cause Time or Memory Limit Exceeded ???
    I think it's the same almost.


  • 0
    Q

    clear and excellent


  • 1
    E

    I ran it. It is 93 ms.
    Not sure if it is the website or something.


  • 1
    K

    My code is the same with yours, however my time is 92 ms.


  • 0
    Z

    @gensmusic said in C++ concise recursive solution C(n,k) ->C(n-1,k-1) / 8ms:

    tart-1

    I think you should use
    combine(i-1, k-1, res, tmp);
    instead of
    combine(start-1, k-1, res, tmp);


Log in to reply
 

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