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

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?

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.