Algorithm to count the number of subsets of size k with sum of all its elements minimum possible

Question

An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible

here the subsets of size k=3 are:- 122 122 122 222

we see that there are 3 subsets having the minimum sum

I did this in bruteforce approach..first I stored the subsets of size k in a vector and then found the sum for each of the subsets and stored them in another vector and then counted the frequency of the minimum element

how to optimize it?

Answer 1

Suppose that you arrange the array in non-decreasing order. It's not hard to check that the minimum sum is obtained by taking the first $k$ elements.

Suppose that the distinct values found in the array are $a_1 < a_2 < \cdots$, where $a_i$ appears $n_i$ times. There is an index $d$ such that $n_1 + \cdots + n_{d-1} < k$ but $n_1 + \cdots + n_d \geq k$. Thus every $k$-subset of minimum sum contains all elements of values $a_1,\ldots,a_{d-1}$, and any $k-(n_1+\cdots+n_{d-1})$ elements of value $a_d$. You take it from here.

• ANKIT SINGHA: could you please elaborate it more clearly with an example,would appreciate that!
• Yuval Filmus: It’s better if you worked it out on your own.

Answer 2

There are 3 minimum subsets, which happens to be the same number as the largest number in the sum. Can you play around with this insight to see if you can find out how to solve it?

For example, if the minimum sum contains both (e.g.) the numbers 5 and 7, then realize that all 5ers have to be included in every minimum sum!