CareerCup

Assumptions:
- There is no negative weight
- Multiple weights can occure as in the smaple given
- I assume first k-weight means max the top-k, according to summed weight

Approach:
- clearly, if the input was sorted according to weight, the highest is the one with all
balls (if no neg. weights)
- the next lower is when excluding the element with least weight
- the next lower is excluding the 2nd lowest weight
- the third is either excluding the 3rd lowest or the 2nd and lowest

The basic idea is pretty straight forward:
- sort input as described above
- maintain a priority queue with the highest combination on top
- When picking an element from that queue, calculate the next options, where it is
not straight forward to decide which will be the next higher one. Put all of them into
the queue, then next loop the highest is picked etc. That is similar to Dijkstra
shortest path. But in order to be efficient, I only calculate next elements when an
item gets picked and this needs a bith of thought, but I can create a tree, similar to
a Fenwick on the fly ...
When an item is picked there are at most two new options, one is to take the next
element, the other is to take the current element and the lowest possible
- For the time complexity, there is the issue we need to produce the results which is
O(n*k). Then there is the sort which is O(n*lg(n)) and the maintenance of the queue which
is O(k*lg(k)). The queue component is irrelevant since always smaller than the sort. Then
there are some copy operations inside the algo, which are executed at most 2k times, thus
resulting in O(k*n). Overall it is O(n*k + n*lg(n)) - depending on the input one or the
other term dominiates.

Cool question, never saw this one, really nice! Although a bit hard to come up with the
"next element" algorithm in 30 minutes together with all the rest.

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;
using uint = unsigned int;

void print_top_k_subsets(const vector<pair<string, uint>>& input, uint k) 
{
	if (input.size() < 1 || k < 1) return;
	uint result_count = 0;

	// sort
	auto sinput(input); // sorted input, smallest weight first
	sort(sinput.begin(), sinput.end(), 
		[](const pair<string, uint>& a, const pair<string, uint>& b) {
		return a.second < b.second;
	});

	// queue with queitem having least loss on top
	struct QueueItem {
		int weight_loss;
		int last_excluded;
		int last_excludable;
		vector<bool> excluded;
	};
	auto qcomp = [](const QueueItem& a, const QueueItem& b) {
		return a.weight_loss > b.weight_loss;
	};
	priority_queue<QueueItem, vector<QueueItem>, decltype(qcomp)> q(qcomp);
	q.push(QueueItem({0, -1, static_cast<int>(sinput.size() - 1), vector<bool>(sinput.size(), false)}));
	
	while (!q.empty() && result_count < k) {
		QueueItem current = q.top(); // copies the vector, not so nice
		q.pop();

		// print result (should be put into a seperate function) 
		result_count++;
		cout << result_count << "th: {";
		int sum = 0;
		bool first = false;
		for (int i = 0; i < sinput.size(); ++i) {
			if (!current.excluded[i]) {
				sum += sinput[i].second;
				cout << (first ? ", " : "") << sinput[i].first;
				first = true;
			}
		}
		cout << "} sum=" << sum << endl;

		// get next potential candidates and put it into the queue
		if (current.last_excluded > 0) {
			QueueItem new_item(current);
			new_item.weight_loss += sinput[0].second;
			new_item.last_excludable = current.last_excluded - 1;
			new_item.last_excluded = 0;
			new_item.excluded[0] = true;
			q.push(new_item);
		}
		if (current.last_excluded < current.last_excludable) {
			if (current.last_excluded >= 0) {
				current.weight_loss -= sinput[current.last_excluded].second;
				current.excluded[current.last_excluded] = false;
			}
			current.last_excluded++;
			current.weight_loss += sinput[current.last_excluded].second;
			current.excluded[current.last_excluded] = true;
			q.push(current);
		}
	}
}


int main()
{
	cout << "sample 1" << endl << "-----------------------------" << endl;
	print_top_k_subsets({ {"red", 4}, {"yellow", 1}, {"green", 2}, {"blue",  2} }, 5);
	cout << "sample 2" << endl << "-----------------------------" << endl;
	print_top_k_subsets({ { "red", 4 },{ "yellow", 1 },{ "green", 2 },{ "blue",  2 }, {"amber", 1}, {"black", 2}, {"white", 1} }, 15);

@Ari. For the example in the description, it would look like:
4, 2, 2, 1, sum = 9
4, 2, 2, , sum = 8
4, 2, , 1, sum = 7
4, 2, , , sum = 6
4, , 2, 1, sum = 7
, which is not correct.

Sort the set.
Now the set of subsets can be manifested by 2to the power n - 1.( Let's say the number is C)
So the combinations are C -k +1 to C in binary format and sum where positions are 1