Valour's blog

Smallest Subsets | csacademy
By Valour, history, 6 years ago, In English

Can someone please explain how to solve this problem.

https://csacademy.com/contest/round-79/task/smallest-subsets/statement/

Thanks in Advance!

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Hello!

    Thanks for your response! sir, your solution is helpful. I was unaware that this can also be done using binary search.

    I too found a solution and would like to share it. It was too get the minimum sum from the given array, which will be sum of all negatives or zero(if no negative element in the array). This will be the sum of smallest sum subset.

    Then, after getting this sum we may consider all elements of the array to be positive and sort the array.

    Now, we can use a priority queue(or set) and insert the minimum sum in it. And, then on each iteration(from 0 to k), we pick the smallest element from the priority queue and remove it, let it be (x), and inplace of it add (x + a[itr+1]) and (x + a[itr+1] — a[itr]) in the priority queue. Where (itr) is the rightmost element chosen from the sorted array.

    Now, in all k iterations the smallest elements picked from the priority queue will give us the k subsets in increasing order of their sum.

    This works as in each iteration we choose one element and remove the previously taken. So, it will form all the subsets possible. And, due to the ordering of the array and the smallest sum subset chosen in each iteration, the subsets formed are in increasing order of sum.

    The image shows how all subsets are evaluated, for 4 elements.

    → Reply