Short Iterative C++ Answer 8ms


  • 75
    H
    class Solution {
    public:
    	vector<vector<int>> combine(int n, int k) {
    		vector<vector<int>> result;
    		int i = 0;
    		vector<int> p(k, 0);
    		while (i >= 0) {
    			p[i]++;
    			if (p[i] > n) --i;
    			else if (i == k - 1) result.push_back(p);
    			else {
    			    ++i;
    			    p[i] = p[i - 1];
    			}
    		}
    		return result;
    	}
    };

  • 0
    C

    Awesome! Could you please give some explanation?


  • 1
    L

    p contains the actual combinations in result. For n = 4, k = 2, p changes in this way:

    0 0 #initialization
    1 0
    1 1 #push_back
    1 2 #push_back
    1 3 #push_back
    1 4 #push_back
    1 5
    2 5
    2 2 #push_back
    2 3 #push_back
    2 4 #push_back
    ...
    3 4 #push_back
    3 5
    4 5
    4 4
    4 5
    5 5 #stop 
    

    As you can see, the code iterates through smallest combination to the largest combination, and returns all qualified combinations.


  • 0
    A

    Great solution, no extra space (except for storing results), the best I've ever seen for this question.


  • 0
    N

    What would be time complexity for this solution ?


  • 0
    X
    vector<vector<int>> combine(int n, int k) {
    
       vector<vector<int>> res;
       vector<int> curr(k,0);
       int i=0;
       while(i>=0 && curr[0]<=(n-k)+1){
           curr[i]++;
           if(curr[i]>n) --i;
           else if(i==k-1) res.push_back(curr);
           else{
               i++;
               curr[i]=curr[i-1];
           }
       }
       return res;
    

    }


  • 1
    X

    Good job! Faster than my iterative one. I ran your code for 11ms. Then I tried to optimized a little bit to get 8ms. What I was doing is to add one more condition curr[0]<=(n-k)+1 to terminate the loop earlier.


  • 0

    could you explain your code?


  • 0
    S

    What a brilliant solution!


  • 2
    R

    The condition curr[i]>n-k+i+1 can reduce the loops for every i.
    class Solution {
    public:
    vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> curr(k, 0);
    int i = 0;
    while (i >= 0){
    curr[i]++;
    if (curr[i]>n - k + i + 1) --i;
    else if (i == k - 1) res.push_back(curr);
    else{
    i++;
    curr[i] = curr[i - 1];
    }
    }
    return res;
    }
    };


  • 19
    G

    This is an excellent solution.

    I added some document comments and inline printouts to help me understand how it works, and thought I'd share.

    #include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    string toString(vector<int> v) {
        string ans = "[";
        for (int i: v) {
            ans += i + '0';
            ans += ", ";
        }
        ans = ans.substr(0, ans.length() - 2) + "]";
        return ans;
    }
    
    string toString(vector<vector<int>> v) {
        string ans = "[";
        for (vector<int> i: v) {
            ans += toString(i);
            ans += ", ";
        }
        ans = ans.substr(0, ans.length() - 2) + "]";
        return ans;
    }
    
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> ans;
            vector<int> c(k, 0); // vector of length k, all 0s
            int i = 0;
            while (i >= 0) {
                // Increment element at index i
                c[i]++;
                cout << "Incremented element at index " << i << endl;
                cout << toString(c) << endl;
                
                /* Move index to the left if the element
                 * at index i has exceeded n.
                 */
                if (c[i] > n) {
                    i--;
                    cout << "n exceeded at " << i+1 << ", moving index to the left" << endl;
                }
                
                /* If the index is at the end of the vector
                 * c, then (because the other conditions are
                 * obeyed), we know we have a valid combination,
                 * so push it to our ans vector<vector<>>
                 */
                else if (i == k - 1) {
                    ans.push_back(c);
                    cout << "Combination found!" << endl;
                    cout << "Added " << toString(c) << " as an answer!" << endl;
                }
                
                /* Move index to the right and set the
                 * element at that index equal to the
                 * element at the previous index.
                 * 
                 * Because of the increment at the beginning
                 * of this while loop, we ensure that the
                 * element at this index will be at least
                 * one more than its neighbor to the left.
                 */
                else {
                    i++;
                    c[i] = c[i - 1];
                    cout << "Moved index to the right, and copied the value"
                    << " from the left" << endl;
                    cout << toString(c) << endl;
                }
            }
            return ans;
        }
    };
    
    int main() {
        Solution sol;
        cout << toString(sol.combine(4, 2)) << endl;
        return 0;
    

    For example, the (4, 2) test case yields:

    Incremented element at index 0
    [1, 0]
    Moved index to the right, and copied the value from the left
    [1, 1]
    Incremented element at index 1
    [1, 2]
    Combination found!
    Added [1, 2] as an answer!
    Incremented element at index 1
    [1, 3]
    Combination found!
    Added [1, 3] as an answer!
    Incremented element at index 1
    [1, 4]
    Combination found!
    Added [1, 4] as an answer!
    Incremented element at index 1
    [1, 5]
    n exceeded at 1, moving index to the left
    Incremented element at index 0
    [2, 5]
    Moved index to the right, and copied the value from the left
    [2, 2]
    Incremented element at index 1
    [2, 3]
    Combination found!
    Added [2, 3] as an answer!
    Incremented element at index 1
    [2, 4]
    Combination found!
    Added [2, 4] as an answer!
    Incremented element at index 1
    [2, 5]
    n exceeded at 1, moving index to the left
    Incremented element at index 0
    [3, 5]
    Moved index to the right, and copied the value from the left
    [3, 3]
    Incremented element at index 1
    [3, 4]
    Combination found!
    Added [3, 4] as an answer!
    Incremented element at index 1
    [3, 5]
    n exceeded at 1, moving index to the left
    Incremented element at index 0
    [4, 5]
    Moved index to the right, and copied the value from the left
    [4, 4]
    Incremented element at index 1
    [4, 5]
    n exceeded at 1, moving index to the left
    Incremented element at index 0
    [5, 5]
    n exceeded at 0, moving index to the left
    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    

  • 0
    T

    This is brilliant! Always thought recursion is a must for backtracking problems, this proved me wrong.


  • 0
    _

    @logicthief those lists with equal number, such as 11 and 22, are not pushed back to result.


  • 0
    L

    Nice solution! But how can you get a execution time of 8ms...


  • 0
    J

    @Lin_Zephyr I think that's 2 years ago. Now testcase is changed.


  • 0
    L

    You are a genius !!!


  • 0
    S

    @logicthief lists such as (1,1) (2,2) are not pushed back to result.


  • 0
    S

    This is not a optimum solution.
    Consider the case n=4, k=4.
    It will try many dead end cases like:
    1,2,4,
    1,3,4
    2,3,4
    2,4,
    3,4
    4


  • 0
    S

    @thsieh10 The optimum iterative solution is using a stack.


  • 0
    E

    Brilliant solution!


Log in to reply
 

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