Count subsequences having average of its elements equal to K | Stores the dp states ; Function to find the count of subsequences having average K ; Base condition ; Three loops for three states ; Recurrence relation ; Stores the sum of dp [ n ] [ j ] [ K * j ] all possible values of j with average K and sum K * j ; Iterate over the range [ 1 , N ] ; Return the final count ; Driver Code
var dp = Array . from ( Array ( 101 ) , ( ) => Array ( 101 ) ) ; for ( var i = 0 ; i < 101 ; i ++ ) for ( var j = 0 ; j < 101 ; j ++ ) dp [ i ] [ j ] = new Array ( 1001 ) . fill ( 0 ) ; function countAverage ( n , K , arr ) { dp [ 0 ] [ 0 ] [ 0 ] = 1 ; for ( var i = 0 ; i < n ; i ++ ) { for ( var k = 0 ; k < n ; k ++ ) { for ( var s = 0 ; s <= 1000 ; s ++ ) { dp [ i + 1 ] [ k + 1 ] [ s + arr [ i ] ] += dp [ i ] [ k ] [ s ] ; dp [ i + 1 ] [ k ] [ s ] += dp [ i ] [ k ] [ s ] ; } } } var cnt = 0 ; for ( var j = 1 ; j <= n ; j ++ ) { cnt += dp [ n ] [ j ] [ K * j ] ; } return cnt ; } var arr = [ 9 , 7 , 8 , 9 ] ; var K = 8 ; var N = arr . length document . write ( countAverage ( N , K , arr ) ) ;