I was writing code for problem 16.5 and noticed that the code for 16.5 in the ebook is slightly different (though correct) than the approach the prior description in 16.5 suggests.
The approach suggested seems to be that all K size subsets of an input set A = union of all K sized subsets from a set {A - e} + {e added to the union of all K-1 sized subsets of {A-e}}
where ‘e’ is an element in the input set A.
The code seems to implement it differently.
13 void all_comb(vector &a, int k, int idx, vector & tmp, vector< vector >& result) {
14
15 if (tmp.size() == k) {
16 result.emplace_back(tmp);
17 }
18
19 int rem = k - tmp.size();
20 for (int i =idx; i < a.size() && rem <= a.size() - i ; i++) {
21 tmp.emplace_back(a[i]);
22 all_comb(a, k, i+1, tmp, result);
23 tmp.pop_back();
24 }
26 }
But the approach described in the book text would instead be something like the following code.
void all_comb(vector &a, int k, int idx, vector & tmp, vector< vector >& result) {
14
15 if (tmp.size() == k) {
16 result.emplace_back(tmp);
17 return;
18 }
19
20 int rem = k-tmp.size();
21 if (rem > a.size() - idx)
22 return;
23
24 tmp.emplace_back(a[idx]);
25 all_comb(a, k, idx+1, tmp, result);
26 tmp.pop_back();
27 all_comb(a, k, idx+1, tmp, result);
28 }
Both approaches would give the same answer, but is there any reason as to why the code presented in the book is different than the description? I’m not sure if it’s on purpose.
It doesn’t seem that one of them would be more efficient than the other.
What would be the reasoning behind the code in the ebook and intuitive way to understand it?
Thanks