C++ 12 ms this time recursive solution


  • 0
    P
    vector<vector<int>> combine(int n, int k)
    {
        vector<vector<int>> result;
        vector<int> combination;
        combineRec(n, k, 1, combination, result);
        return result;
    }
    
    
    void combineRec(int n, int k, int curN, vector<int> & combination, vector<vector<int>> & result) 
    {
        if (combination.size() == k)
        {
            result.push_back(combination);
            return;
        }
        
        for(int i = curN; i <= n; ++i)
        {
            combination.push_back(i);
            combineRec(n, k, i + 1, combination, result);
            combination.erase(combination.end()-1);
        }
    }

  • 0

    Cost 244ms!! What is going on here?!


  • 0

    No wonder quite similar solution of mine cost 99ms, so weird.

    class Solution {
    private:
        void search(int n, int pos, int k, vector<int>&v, vector<vector<int>>& vv)
        {
            if(k == 0) 
            {
                vv.push_back(v);
                return ;
            }
            for(int i = pos; i <= n-k+1; ++i)
            {
                v.push_back(i);
                search(n, i+1, k-1, v, vv);
                v.pop_back();
            }
        }
    public:
        vector<vector<int>> combine(int n, int k) 
        {
            vector<int> v;
            vector<vector<int>> vv;
            search(n, 1, k, v, vv);
            return vv;
        }
    };

Log in to reply
 

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