CPP solution: traverse from [1,2] to [3,4]

• ``````class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> ans;
if (k > n)
return ans;

vector<int> v(k, 0);
for (int iii = 0; iii < k; iii++)
v[iii] = iii + 1;
ans.push_back(v);

while (1) {
bool finish = true;
for (int iii = 0; iii < v.size(); iii++) {
if (v[iii] != n - k + iii + 1) {
finish = false;
break;
}
}
if (finish) {
return ans;
}

for (int iii = v.size() - 1; iii >= 0; iii--) {
if (v[iii] != n - k + iii + 1) {
v[iii]++;
for (int jjj = iii + 1; jjj < v.size(); jjj++) {
v[jjj] = v[jjj - 1] + 1;
}
ans.push_back(v);
break;
}
}

}
}
};``````

• Here are my solutions:

https://github.com/loverszhaokai/ALG/blob/master/src/combinations.cc

Feel free to give me any advice.

• Wrote my own version. It's quite similar but also somewhat different.

``````vector<vector<int>> combine(int n, int k) {
vector<int> comb;
for (int i=1; i<=k; i++)
comb.push_back(i);
vector<vector<int>> combs(1, comb);
while (true) {
int i = k - 1;
while (i >= 0 && comb[i] - i == n - k + 1)
i--;
if (i < 0)
return combs;
comb[i]++;
while (++i < k)
comb[i] = comb[i-1] + 1;
combs.push_back(comb);
}
}
``````

And a Python version:

``````def combine(self, n, k):
comb = range(1, k+1)
combs = [comb[:]]
while True:
i = k - 1
while i >= 0 and comb[i] - i == n - k + 1:
i -= 1
if i < 0:
return combs
comb[i:] = range(comb[i]+1, comb[i]+1+k-i)
combs += comb[:],
``````

• Why `iii` instead of the usual `i`?

• Oh, both are ok. I use iii instead of i just to make it clear, since i, j, k ... are always confusing.

• Also, iii is easy for searching than i.

• Very good! Your solution is more compact!

After looked through your solution, I found that mine was wasting time on searching the last index which was not the max value of its position.

I think your solution will be better if you can save some time on initing com.

``````vector<vector<int>> combine(int n, int k) {
vector<int> comb(k, 0);
for (int i=1; i<=k; i++)
comb[i - 1] = i;
...
}``````

• I thought about doing that, don't remember why I didn't. I don't think it'll be noticeably faster, though, if at all. I mean, it's just the initialization.

• Ah, yes, for searching it's definitely nice :-). Though a good IDE should be able to find exactly every occurrence even if it's just `i`.

• Yes it has little impact.

• Yes, a good IDE will be, such as visual studio 2013. But I use emacs. :)

• Heh, yeah, I currently use Notepad++ :-)

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