K-subsets

Questions 1 to 5 of 6

1. 1. What does this program print? ``cpp #include <iostream> #include <vector> using namespace std; void choose(const vector<int>& a, int k, int start, vector<int>& cur, vector<vector<int>>& out) { if ((int)cur.size() == k) { out.push_back(cur); return; } for (int i = start; i < (int)a.size(); i++) { cur.push_back(a[i]); choose(a, k, i + 1, cur, out); cur.pop_back(); } } int main() { vector<int> a = {1, 2, 3}; vector<int> cur; vector<vector<int>> out; choose(a, 2, 0, cur, out); cout << out.size() << " " << out.back()[0] << out.back()[1] << "\n"; } ``

   3 133 236 233 32
2. 2. What does this program print? It is the same program as above, except the recursive call is changed to choose(a, k, i, cur, out);. ``cpp #include <iostream> #include <vector> using namespace std; void choose(const vector<int>& a, int k, int start, vector<int>& cur, vector<vector<int>>& out) { if ((int)cur.size() == k) { out.push_back(cur); return; } for (int i = start; i < (int)a.size(); i++) { cur.push_back(a[i]); choose(a, k, i, cur, out); cur.pop_back(); } } int main() { vector<int> a = {1, 2, 3}; vector<int> cur; vector<vector<int>> out; choose(a, 2, 0, cur, out); cout << out.size() << " " << out.back()[0] << out.back()[1] << "\n"; } ``

   3 339 336 336 23
3. 3. The formula for the number of ways to choose k items from n is written C(n, k). How is C(n, k) read aloud?

   Type your answer.

4. 4. To stop a group from picking the same item twice, the recursive call passes ___ as its new start index.

   Type your answer.

5. 5. The search for three numbers from 1 to 9 that add up to 15 makes 130 calls in total. How many of those calls are leaves, meaning calls that hold a full group of three?

   46848130