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.

#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!/((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);
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;
}