Count of binary arrays of size N with sum of product of adjacent pairs equal to K | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int combinationsPossible ( int N , int idx , int prev , int val , int K , vector < vector < vector < 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 ) ; } return dp [ val ] [ idx ] [ prev ] = ans ; } int main ( ) { int N = 5 ; int K = 3 ; vector < vector < vector < int > > > dp ( K + 1 , vector < vector < int > > ( N + 1 , vector < int > ( 2 , -1 ) ) ) ; cout << ( combinationsPossible ( N , 0 , 0 , 0 , K , dp ) + combinationsPossible ( N , 0 , 1 , 0 , K , dp ) ) ; }