My C++ code (10ms, non-recursive)


  • 0
    D

    The idea is to generate all the unique ascending sequences (i.e. s[0]< s[1]<...< s[k-1]). Firstly, inserting the sequence {1,2,..,k} as a seed and try to increase s[i] (i from k-1 to 0) to generate all the different combinations, which have to meet the criterion s[i] < s[i+1]

       class Solution {
        public:
            vector<vector<int> > combine(int n, int k) {
                vector<vector<int> > res;
                int i, j, offset, len;
                
                if(n>=k)
                {
                    res.push_back(vector<int> (k, 1));
                    for(i=1; i<=k; i++) res[0][i-1] = i; // insert the seed sequence {1,2,...k}
                }
                
                if(n>k)
                {
                    int level = k-1;
                    while(level>=0) // scan all the levels from k-1 to 0
                    {
                        int len = res.size();
                        for(i=res.back()[level]+1;i<=n;i++) // i is all possible values for s[level]
                        {
                            for(j=0;j<len;j++) // scan all the candidate sequences generated already
                            {
                                if( (level==(k-1)) || i < res[j][level+1]) // if a valid ascending sequence can be generated 
                                {
                                    res.push_back(res[j]);
                                    res.back()[level] = i;
                                }
                            }
                        }
                        level--;
                    }
                }
                return res;
            }
        };

Log in to reply
 

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