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

**#include<iostream>
#include<algorithm>**
**using namespace** std;
*/* find the sum of maximum values in all possible subsets of
given size
for e.g : arr = {3,1,5,7}
all possible subsets of size 3 are:-
subset max element
{3,1,5} 5
{3,1,7} 7
{3,5,7} 7
{1,5,7} 7
Sum of max element :: 5+7+7+7 = 26
Logic :-
Sort the input array 'arr[]'
Suppose array size = n & subset size = k
For (k <= i < n), [ find the no. of times arr(i) appears as max value
in some subsets; this value is given by C(i,k) ] and sum up all the values.
We precompute the values of C(i,k) in a binomial matrix
*/*
**int** sumOfMaxValueInAllSubsets(**int** arr[],**int** size,**int** subset_size) {
*// sort the input array*
sort(arr,arr+size);
*// matrix to store the binomial coefficients
// binomial[i][j] = C(i,j)
// for e.g. binomial[4][2] = 4!/((4-2)! * 2!) = 2*
**int** **binomial;
**int** i,j;
**int** sum = 0;
binomial = **new int***[size];
**for** (i=0;i<size;i++) {
binomial[i] = **new int**[subset_size];
}
*// precomputation of all binomial matrix using standard
// recursive formula :- C(n,r) = C(n-1,r-1) + C(n-1,r)*
**for** (i=0;i<size;i++) {
**for** (j=0;j<subset_size;j++) {
**if** (i == j || j == 0) {
*//C(n,n) = C(n,0) = 1*
binomial[i][j] = 1;
}
**else if** (i < j) {
*// invalid condition
// we are initializing it to 0
// won't be used in actual computation *
binomial[i][j] = 0;
}
**else** {
*// as per standard recursive formula*
binomial[i][j] = binomial[i-1][j-1] + binomial[i-1][j];
}
}
}
**for** (i=subset_size-1;i<size;i++) {
*// let x = binomial[i][subset_size-1]
// then, arr[i] appears as max element in x subsets of size 'subset_size'
// subset_size-1 denotes the array index starting from 0*
sum += arr[i]*binomial[i][subset_size-1];
}
**return** sum;
}
*// main*
**int** main() {
**int** arr[] = {3,1,5,7};
**int** size = **sizeof**(arr)/**sizeof**(arr[0]);
**int** subset_size = 3;
**int** sum = sumOfMaxValueInAllSubsets(arr,size,subset_size);
cout<<"\nSum of max values in all subsets of size "<<subset_size <<" is "<<sum;
cout<<endl;
**return** 0;
}