Count even length binary sequences with same sum of first and second half bits | A memoization based Java 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 memset ( lookup , - 1 , sizeof ( lookup ) ) ; ; call countSeqUtil ( ) ; Driver program
import java . io . * ; class GFG { static int lookup [ ] [ ] = new int [ 1000 ] [ 1000 ] ; static int countSeqUtil ( int n , int dif ) { if ( Math . abs ( dif ) > n ) return 0 ; if ( n == 1 && dif == 0 ) return 2 ; if ( n == 1 && Math . 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 ; } static int countSeq ( int n ) { for ( int k = 0 ; k < lookup . length ; k ++ ) { for ( int j = 0 ; j < lookup . length ; j ++ ) { lookup [ k ] [ j ] = - 1 ; } } return countSeqUtil ( n , 0 ) ; } public static void main ( String [ ] args ) { int n = 2 ; System . out . println ( " Count ▁ of ▁ sequences ▁ is ▁ " + countSeq ( 2 ) ) ; } }