Number of ways to partition a string into two balanced subsequences | For maximum length of input string ; Declaring the DP table ; Function to calculate the number of valid assignments ; Return 1 if both subsequences are balanced ; Increment the count if it an opening bracket ; Decrement the count if it a closing bracket ; Driver Code ; Initial value for c_x and c_y is zero
let MAX = 10 ; let F = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { F [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) { F [ i ] [ j ] = new Array ( MAX ) ; for ( let k = 0 ; k < MAX ; k ++ ) { F [ i ] [ j ] [ k ] = - 1 ; } } } function noOfAssignments ( s , n , i , c_x , c_y ) { if ( F [ i ] [ c_x ] [ c_y ] != - 1 ) return F [ i ] [ c_x ] [ c_y ] ; if ( i == n ) { F [ i ] [ c_x ] [ c_y ] = ( c_x == 0 && c_y == 0 ) ? 1 : 0 ; return F [ i ] [ c_x ] [ c_y ] ; } if ( s . charAt ( i ) == ' ' ) { F [ i ] [ c_x ] [ c_y ] = noOfAssignments ( s , n , i + 1 , c_x + 1 , c_y ) + noOfAssignments ( s , n , i + 1 , c_x , c_y + 1 ) ; return F [ i ] [ c_x ] [ c_y ] ; } F [ i ] [ c_x ] [ c_y ] = 0 ; if ( c_x != 0 ) F [ i ] [ c_x ] [ c_y ] += noOfAssignments ( s , n , i + 1 , c_x - 1 , c_y ) ; if ( c_y != 0 ) F [ i ] [ c_x ] [ c_y ] += noOfAssignments ( s , n , i + 1 , c_x , c_y - 1 ) ; return F [ i ] [ c_x ] [ c_y ] ; } let s = " " ; let n = s . length ; document . write ( noOfAssignments ( s , n , 0 , 0 , 0 ) ) ;