Count subsequences having average of its elements equal to K | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 101 ] [ 101 ] [ 1001 ] ; 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 <= 1000 ; 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 ; } int main ( ) { int arr [ ] = { 9 , 7 , 8 , 9 } ; int K = 8 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countAverage ( N , K , arr ) ; return 0 ; }