1
$\begingroup$

For e.g if the array is 2,2,3,3,5 and k=3 there are total 18 subequences 1 subequence of length 0(i.e empty subsequence) 5 subsequences of length 1

8 subsequences with length 2

4 subsequences with length 3

how to proceed?

$\endgroup$
  • 2
    $\begingroup$ It's better if you spent more time trying to solve your questions before posting them here. $\endgroup$ – Yuval Filmus Sep 8 at 19:30
  • $\begingroup$ i did spend 4 days on this one and what i observed is that i could use binomial coefficients to solve this one but only some of my test cases are getting passed....so i thought maybe someone could give me a better approach $\endgroup$ – ANKIT SINGHA Sep 9 at 3:37
1
$\begingroup$

You can solve this using dynamic programming. Let me show instead the solution using generating functions, which can also be implemented using dynamic programming.

Suppose that there are $m$ distinct values in the array, appearing $n_1,\ldots,n_m$ times. The generating function $$ \prod_{i=1}^m (1+n_ix) $$ counts the number of subsequences with distinct values of size $k$, in the sense that this is the coefficient of $x^k$. For example, in your case $m = 3$ and $n_1=n_2=2,n_3=1$. Therefore the generating function is $$ (1+2x)^2(1+x) = (1+4x+4x^2)(1+x) = 1+5x+8x^2+4x^3. $$

$\endgroup$
  • $\begingroup$ Yes,thankyou...i too had the same approach but slightly wrong...now i'll try to code it $\endgroup$ – ANKIT SINGHA Sep 9 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.