Count of binary arrays of size N with sum of product of adjacent pairs equal to K | Java program for the above approach ; 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
import java . util . * ; class GFG { static int combinationsPossible ( int N , int idx , int prev , int val , int K , int [ ] [ ] [ ] dp ) { if ( val > K ) { return 0 ; } if ( dp [ val ] [ idx ] [ prev ] != - 1 ) { return dp [ val ] [ idx ] [ prev ] ; } if ( idx == N - 1 ) { if ( val == K ) { return 1 ; } return 0 ; } int ans = 0 ; if ( prev == 1 ) { ans += combinationsPossible ( N , idx + 1 , 1 , val + 1 , K , dp ) ; ans += combinationsPossible ( N , idx + 1 , 0 , val , K , dp ) ; } else { ans += combinationsPossible ( N , idx + 1 , 1 , val , K , dp ) ; ans += combinationsPossible ( N , idx + 1 , 0 , val , K , dp ) ; } dp [ val ] [ idx ] [ prev ] = ans ; return dp [ val ] [ idx ] [ prev ] ; } public static void main ( String [ ] args ) { int N = 5 ; int K = 3 ; int [ ] [ ] [ ] dp = new int [ K + 1 ] [ N + 1 ] [ 2 ] ; for ( int i = 0 ; i < K + 1 ; i ++ ) { for ( int j = 0 ; j < N + 1 ; j ++ ) { for ( int k = 0 ; k < 2 ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; } } System . out . print ( combinationsPossible ( N , 0 , 0 , 0 , K , dp ) + combinationsPossible ( N , 0 , 1 , 0 , K , dp ) ) ; } }