andmej wrote:By the way, nice problem Sohel.

Thanks!

And about the solution:

Let's talk about another problem. Given N integers, how many way can you choose M integers whose sum exceeds S.

Let N = 6 and M = 4 and the set of numbers = { 1, 2, 6, 7, 10, 12 }. And also assume that S = 10.

The first thing is to divide these numbers into two sets arbitrarily. Lets consider like this :: A = {1, 2, 6} and B{7, 10, 12}.

The next thing to do is find all combinations in each set. That is 2^3 numbers in each set. Lets call these new sets AA and BB.

AA = {0, 1, 2, 6, 1+2, 1+6, 2+6, 1+2+6} = {0, 1, 2, 6, 3, 7, 8, 9}. Do the same thing with B to get BB.

Now pick each element in AA and find the other part in BB using binary search. Suppose we picked '2' from AA. Since the sum is 10, we'd be looking for how many numbers are there in BB whose value is at least 9 so that the total sum exceeds 10.

One thing to keep in mind is the number of integers that make up each combination. For example, taking 2 from AA means we have to look for values in BB whose elements are exactly made of 3 integers so that total number of elements taken is 4(1+3 :: 1 from AA and 3 from BB }.

The explanation might be a little esoteric but I hope it's enough to get you started.