Non-recursive solution with complexity of time(O(k*C(n,k)))/memory(O(1))


  • 0
    S

    class Solution {
    public:

    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> >ret;
        if(k>n||k<=0)return ret;
        
        for(int i=1;i<=n-k+1;i++){
            ret.push_back(vector<int>(1,i));
        }
        
        for(int i=2;i<=k;i++){
            int num=ret.size();
            for(int j=0;j<num;j++){
                int last=ret[j].back();
                vector<int> pretmp=ret[j];
                ret[j].push_back(last+1);
                for(int p=last+2;p+k-i<=n;p++){
                    vector<int> tmp=pretmp;
                    tmp.push_back(p);
                    ret.push_back(tmp);
                }
            }
        }
        
        return ret;
    }
    

    };


Log in to reply
 

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