# algorithm for number of subsequences containing at most k numbers with no element repeated in each of the subsequence

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?

• It's better if you spent more time trying to solve your questions before posting them here. – Yuval Filmus Sep 8 at 19:30
• 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 – ANKIT SINGHA Sep 9 at 3:37

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.$$