Count even length binary sequences with same sum of first and second half bits | 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 ; let 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
let lookup = new Array ( 1000 ) ; for ( let i = 0 ; i < 1000 ; i ++ ) { lookup [ i ] = new Array ( 1000 ) ; } function countSeqUtil ( n , 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 ; } function countSeq ( n ) { for ( let k = 0 ; k < lookup . length ; k ++ ) { for ( let j = 0 ; j < lookup . length ; j ++ ) { lookup [ k ] [ j ] = - 1 ; } } return countSeqUtil ( n , 0 ) ; } let n = 2 ; document . write ( " " + countSeq ( 2 ) ) ;