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
dp = [ [ [ 0 for i in range ( 1001 ) ] for i in range ( 101 ) ] for i in range ( 101 ) ] NEW_LINE def countAverage ( n , K , arr ) : NEW_LINE INDENT global dp NEW_LINE dp [ 0 ] [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for k in range ( n ) : NEW_LINE INDENT for s in range ( 100 ) : NEW_LINE INDENT dp [ i + 1 ] [ k + 1 ] [ s + arr [ i ] ] += dp [ i ] [ k ] [ s ] NEW_LINE dp [ i + 1 ] [ k ] [ s ] += dp [ i ] [ k ] [ s ] NEW_LINE DEDENT DEDENT DEDENT cnt = 0 NEW_LINE for j in range ( 1 , n + 1 ) : NEW_LINE INDENT cnt += dp [ n ] [ j ] [ K * j ] NEW_LINE DEDENT return cnt NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 9 , 7 , 8 , 9 ] NEW_LINE K = 8 NEW_LINE N = len ( arr ) NEW_LINE print ( countAverage ( N , K , arr ) ) NEW_LINE DEDENT