The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Miscellaneous

Problem :-
Given a set with 'n' elements. Find the sum of maximum elements in all subsets of size ' p ' such that p <= n.
Consider the array { 3, 1, 5, 7 }. Here, n = 4. Let p = 3.
All possible subsets of size p = 3 are :-
{ 3, 1, 5 } ( Maximum element = 5 )
{ 3, 1, 7 } ( Maximum element = 7 )
{ 3, 5, 7 } ( Maximum element = 7 )
{ 1, 5, 7 } ( Maximum element = 7 )
Sum of maximum elements = 5 + 7 + 7 + 7 = 26

Solution :-
A naive approach to solve the problem would be to find all possible subsets of size p, extract the maximum elements from all the subsets and add them. This approach is very inefficient for large values of p and n .
The interesting thing to note here is that we need not compute all possible subsets just for getting maximum elements. We will approach the problem in a different manner.
First we will sort the array. Then, for element in each index i in the sorted array ( such that p <= i < n ), we will find out in how many subsets can the ' i 'th element appears as the maximum element.
This value is given by C ( i , p ) . We can pre-compute the values of C ( i , p ) for different values of i in a binomial matrix using the recursive formula C( n , r ) = C ( n - 1 , r - 1 ) + C ( n - 1 , r ).
See the implementation below.