# Short Iterative C++ Answer 8ms

• ``````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;
}
};``````

• Awesome! Could you please give some explanation?

• 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.

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

• What would be time complexity for this solution ?

• ``````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;
``````

}

• 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.

• could you explain your code?

• What a brilliant solution!

• 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;
}
};

• 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!
Incremented element at index 1
[1, 3]
Combination found!
Incremented element at index 1
[1, 4]
Combination found!
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!
Incremented element at index 1
[2, 4]
Combination found!
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!
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]]
``````

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

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

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

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

• You are a genius !!!

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

• 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

• @thsieh10 The optimum iterative solution is using a stack.

• Brilliant solution!

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