Chef And Subsequences(RECNDSUB)

Here let the number of positive numbers be p, the negative be q and let the terms equal to zero be z. Now all the subsequences with sum r can be expressed as the coefficient of x^r in (1+x)^p*(1+1/x)^q. Which in turn simplifies to (1+x)^(p+q)/x^q. So to get the coefficient of r the answer would be (p+q)C(q+r)*(2^z),for -q<=r<=p,as each zero can either be included or left out. For handling the case when r=0, you need to take a little care. PS:- I missed by 5 minutes just because of when r=0.Hope you find it useful:).

3 Likes