Can someone please help me out with the solution of this problem "Natsya decided to visit a local store, which has n items. The i-th item has price a[i]
She has to buy k items out of the n items such that total price of all the items bought is minimum.
In how ways she can buy k items such that the overall price is minimum?"
1<=k<=n<=50 a[i]<=n
I have tried to solve it but it is failing in some hidden cases Code.
This is just number of subsequence with K elements with minimum sum. You can do this with dp.
How Dp ? Its greedy
right, my bad, i misread the statement that we can select any number of elements with sum K. But since number of elements selected is K its just simple combinations
Using maps, maximum value elements that belongs to K chosen
ways = totalFreq C usedFreq C = combinations NCR = n!/r!*(n-r)! try using mod (1e9+7) if exceeding limitconstraint
first find out the frequency of each element in the store and store it in a map. also find the minimum cost. now you need to use simple permutation and combinations. suppose you had 4 items with price 2 and you are only buying 2 items , then you can doit in 4c2 ways