Link to the problem :-
Solution:-
1)If say for a given “i” , the size of i'th set is “3” and the elements are :- {2,4,7} …[You keep these elements in sorted order]
2)Now the answer of this set will be summation of count of all the sets whose size is less than “3” .We can easily store the counts of number of sets whose size was “1”, “2” , “3” , “4” and “5” using an array like :- int a[7];
3)In this particular case, answer is : - a[1]+a[2].
4)Now, for all the sets whose size>=3, example a size-4-set:- {2,4,5,7} …
We need to know the number of sets of size “4” which has {2,4,7} in it and the problem is solved!!!..[Same we do with sets of size-“5” and size-“3”]…
5)How do we do it?
We generate all combinations of set of size-“4” of 3 elements :–>
{2,4,5}
{2,4,7}
{4,5,7}
…and store their frequency in a map…We are done!!
Similarly, we generate all combinations of set of size-“4” of “1” and “2” and “3” and “4” elements!!
6)We do the same thing for set of all sizes {1,2,3,4,5 only…}
7)Link to my AC code:- k2A2KB - Online C++0x Compiler & Debugging Tool - Ideone.com
8)Happy-Coding !
Note:- Final Answer:–> a[1]+a[2]+ f3 + f4 + f5 for our current set, calculate this value for all the “n”-sets and add them up!!