Question about 16.6 in 1.4.7

#1

If I develop a solution based on 16.5, wouldn’t it be easier to read than solution 16.6?

vector<vector<int>> Combinations(int n, int k) {
	vector<vector<int>> result;
	vector<int> ans;
	CombinationsHelper(n, k, 1, &ans, &result);
	return result;
}

void CombinationsHelper(int n, int k, int start, vector<int>* ans,
	vector<vector<int>>* result) {
	if (ans->size() == k) {
		result->emplace_back(*ans);
		return;
	}

	for (int i = start; i <= n; i++)
	{
		ans->emplace_back(i);
		CombinationsHelper(n, k, i + 1, ans, result);
		ans->pop_back();
	}
}

The original solution produces subsets in descending order but the elements within the subsets are ascending, which makes the code a bit harder to follow.

0 Likes
#2

I think it is better in the sense that it merges the logic of select and unselect. However, your code misses the optimization of checking the available elements are enough, which I think you probably can figure it out by referencing the original code, and I would like to leave this to you as the homework.

1 Like
#3

I get it now. The original solution puts answer elements to the call stack and tries to reach as far as possible and then work backwards. This gets rid of the scenario that elements are appended to the answer but finally found out there’s not enough of them. Here’s my modified code -

for (int i = start; i <= n && k - ans->size() <= n - i + 1; i++)
{
	ans->emplace_back(i);
	CombinationsHelper(n, k, i + 1, ans, result);
	ans->pop_back();
}

Thanks a lot Tsung-Hsien.

1 Like