Count of binary arrays of size N with sum of product of adjacent pairs equal to K | Function to return the number of total possible combinations of 0 and 1 to form an array of size N having sum of product of consecutive elements K ; If value is greater than K , then return 0 as no combination is possible to have sum K ; Check if the result of this recursive call is memoised already , if it is then just return the previously calculated result ; Check if the value is equal to K at N , if it is then return 1 as this combination is possible . Otherwise return 0. ; If previous element is 1 ; If current element is 1 as well , then add 1 to value ; If current element is 0 , then value will remain same ; If previous element is 0 , then value will remain same irrespective of the current element ; Memoise and return the ans ; Driver Code ; As the array can be started by 0 or 1 , so take both cases while calculating the total possible combinations
def combinationsPossible ( N , idx , prev , val , K , dp ) : NEW_LINE INDENT if ( val > K ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ val ] [ idx ] [ prev ] != - 1 ) : NEW_LINE INDENT return dp [ val ] [ idx ] [ prev ] NEW_LINE DEDENT if ( idx == N - 1 ) : NEW_LINE INDENT if ( val == K ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT ans = 0 NEW_LINE if ( prev == 1 ) : NEW_LINE INDENT ans += combinationsPossible ( N , idx + 1 , 1 , val + 1 , K , dp ) NEW_LINE ans += combinationsPossible ( N , idx + 1 , 0 , val , K , dp ) NEW_LINE DEDENT else : NEW_LINE INDENT ans += combinationsPossible ( N , idx + 1 , 1 , val , K , dp ) NEW_LINE ans += combinationsPossible ( N , idx + 1 , 0 , val , K , dp ) NEW_LINE DEDENT dp [ val ] [ idx ] [ prev ] = ans NEW_LINE return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE K = 3 NEW_LINE dp = [ [ [ - 1 for i in range ( 2 ) ] for j in range ( N + 1 ) ] for k in range ( K + 1 ) ] NEW_LINE print ( combinationsPossible ( N , 0 , 0 , 0 , K , dp ) + combinationsPossible ( N , 0 , 1 , 0 , K , dp ) ) NEW_LINE DEDENT