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
using System ; using System . Collections . Generic ; class GFG { static int MAX_INDEX = 51 ; static int MAX_SUM = 2505 ; static int [ , , ] dp = new int [ MAX_INDEX , MAX_SUM , MAX_INDEX ] ; static int waysutil ( int index , int sum , int count , List < 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 ; } static int ways ( int N , int K , int [ ] arr ) { List < int > Arr = new List < int > ( ) ; Arr . Add ( - 1 ) ; for ( int i = 0 ; i < N ; ++ i ) { Arr . Add ( arr [ i ] ) ; } for ( int i = 0 ; i < MAX_INDEX ; i ++ ) { for ( int j = 0 ; j < MAX_SUM ; j ++ ) { for ( int l = 0 ; l < MAX_INDEX ; l ++ ) { dp [ i , j , l ] = - 1 ; } } } int answer = waysutil ( N , 0 , 0 , Arr , K ) ; return answer ; } public static void Main ( String [ ] args ) { int [ ] arr = { 3 , 6 , 2 , 8 , 7 , 6 , 5 , 9 } ; int N = arr . Length ; int K = 5 ; Console . WriteLine ( ways ( N , K , arr ) ) ; } }