Count subsequences having average of its elements equal to K | Java program for the above approach ; 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
import java . util . * ; class GFG { static int [ ] [ ] [ ] dp = new int [ 101 ] [ 101 ] [ 1001 ] ; static int countAverage ( int n , int K , int [ ] arr ) { dp [ 0 ] [ 0 ] [ 0 ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int k = 0 ; k < n ; k ++ ) { for ( int s = 0 ; s <= 100 ; s ++ ) { dp [ i + 1 ] [ k + 1 ] [ s + arr [ i ] ] += dp [ i ] [ k ] [ s ] ; dp [ i + 1 ] [ k ] [ s ] += dp [ i ] [ k ] [ s ] ; } } } int cnt = 0 ; for ( int j = 1 ; j <= n ; j ++ ) { cnt += dp [ n ] [ j ] [ K * j ] ; } return cnt ; } public static void main ( String [ ] args ) { int arr [ ] = { 9 , 7 , 8 , 9 } ; int K = 8 ; int N = arr . length ; System . out . print ( countAverage ( N , K , arr ) ) ; } }