Number of ways to choose elements from the array such that their average is K | C ++ implementation of the above approach ; This dp array is used to store our values so that we don 't have to calculate same values again and again ; Base cases Index can 't be less than 0 ; No element is picked hence average cannot be calculated ; If remainder is non zero , we cannot divide the sum by count i . e . the average will not be an integer ; If we find an average return 1 ; If we have already calculated this function simply return it instead of calculating it again ; If we don 't pick the current element  simple recur for index -1 ; If we pick the current element add it to our current sum and increment count by 1 ; Store the value for the current function ; Function to return the number of ways ; Push - 1 at the beginning to make it 1 - based indexing ; Initialize dp array by - 1 ; Call recursive function waysutil to calculate total ways ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX_INDEX  51 NEW_LINE #define MAX_SUM  2505 NEW_LINE int dp [ MAX_INDEX ] [ MAX_SUM ] [ MAX_INDEX ] ; int waysutil ( int index , int sum , int count , vector < int > & arr , int K ) { if ( index < 0 ) return 0 ; if ( index == 0 ) { if ( count == 0 ) return 0 ; int remainder = sum % count ; if ( remainder != 0 ) return 0 ; int average = sum / count ; if ( average == K ) return 1 ; } if ( dp [ index ] [ sum ] [ count ] != -1 ) return dp [ index ] [ sum ] [ count ] ; int dontpick = waysutil ( index - 1 , sum , count , arr , K ) ; int pick = waysutil ( index - 1 , sum + arr [ index ] , count + 1 , arr , K ) ; int total = pick + dontpick ; dp [ index ] [ sum ] [ count ] = total ; return total ; } int ways ( int N , int K , int * arr ) { vector < int > Arr ; Arr . push_back ( -1 ) ; for ( int i = 0 ; i < N ; ++ i ) { Arr . push_back ( arr [ i ] ) ; } memset ( dp , -1 , sizeof dp ) ; int answer = waysutil ( N , 0 , 0 , Arr , K ) ; return answer ; } int main ( ) { int arr [ ] = { 3 , 6 , 2 , 8 , 7 , 6 , 5 , 9 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 5 ; cout << ways ( N , K , arr ) ; return 0 ; }