### Valour's blog

By Valour, history, 8 months ago, ,

Can someone please explain how to solve this problem.

 » 8 months ago, # |   +11 Let's assume that all elements are non-negative.Let's binary search for the value of the largest (sum) subset. Denote the current value to be checked p. How do we check if there exist at least k subsets of sum less than or equal to p?The trick is to modify the usual recursive subset generating method: GenerateSubsets(int i, int currentSum, int p) { add currentSum to list of subsets; if (i == n) return; for (int j = i; j < n; ++j) { if (currentSum + a[j] > p) break; // has to sort a beforehand GenerateSubsets(j + 1, currentSum + a[j]); // takes the j-th element if (list of subsets size is equal to k) break; // IMPORTANT } } This way every time you recurse in, you are guaranteed with a satisfying subset and you stop once you generate enough k subsets or you can't generate any more from the current branch.What if we have negative elements though? Fortunately there is an easy fix. Initialize currentSum = sum of all negative elements, then treat all elements as non-negative. Convince yourself why this is correct.