A simple C++ backtracking solution in 76ms


  • 0
    D
    void helper(int n, int k, int start,vector<vector<int>>& res, vector<int>& temp){
         
            if(k==0){
                res.push_back(temp);
                return;
            }
            for(int i=start;i+k-1<=n;i++){
                temp.push_back(i);    //push the combinations
                helper(n,k-1,i+1,res,temp);
                temp.pop_back();        //backtrack and pop_back
                
            }
        }
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> res;
            vector<int> temp;
            int start=1;
            helper(n,k,start,res,temp);
            return res;
        }
    

  • 0
    Z

    Speed up by pre initializing the size of the vector-we know it will be k. No need for the slow pop-back, just write over the appropriate index


Log in to reply
 

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