Count even length binary sequences with same sum of first and second half bits | A memoization based C ++ program to count even length binary sequences such that the sum of first and second half bits is same ; A lookup table to store the results of subproblems ; dif is difference between sums of first n bits and last n bits i . e . , dif = ( Sum of first n bits ) - ( Sum of last n bits ) ; We can 't cover difference of more  than n with 2n bits ; n == 1 , i . e . , 2 bit long sequences ; Check if this subproblem is already solved n is added to dif to make sure index becomes positive ; int res = First bit is 0 & last bit is 1 ; First and last bits are same ; First bit is 1 & last bit is 0 ; Store result in lookup table and return the result ; A Wrapper over countSeqUtil ( ) . It mainly initializes lookup table , then calls countSeqUtil ( ) ; Initialize all entries of lookup table as not filled ; call countSeqUtil ( ) ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000 NEW_LINE int lookup [ MAX ] [ MAX ] ; int countSeqUtil ( int n , int dif ) { if ( abs ( dif ) > n ) return 0 ; if ( n == 1 && dif == 0 ) return 2 ; if ( n == 1 && abs ( dif ) == 1 ) return 1 ; if ( lookup [ n ] [ n + dif ] != -1 ) return lookup [ n ] [ n + dif ] ; countSeqUtil ( n - 1 , dif + 1 ) + 2 * countSeqUtil ( n - 1 , dif ) + countSeqUtil ( n - 1 , dif - 1 ) ; return lookup [ n ] [ n + dif ] = res ; } int countSeq ( int n ) { memset ( lookup , -1 , sizeof ( lookup ) ) ; return countSeqUtil ( n , 0 ) ; } int main ( ) { int n = 2 ; cout << " Count ▁ of ▁ sequences ▁ is ▁ " << countSeq ( 2 ) ; return 0 ; }