Number of ways to partition a string into two balanced subsequences | C ++ implementation of the above approach ; 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 ; Initializing the DP table ; Initial value for c_x and c_y is zero
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 10 ; int F [ MAX ] [ MAX ] [ MAX ] ; int noOfAssignments ( string & S , int & n , int i , int c_x , int 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 && ! c_y ; return F [ i ] [ c_x ] [ c_y ] ; } if ( S [ 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 ) F [ i ] [ c_x ] [ c_y ] += noOfAssignments ( S , n , i + 1 , c_x - 1 , c_y ) ; if ( c_y ) F [ i ] [ c_x ] [ c_y ] += noOfAssignments ( S , n , i + 1 , c_x , c_y - 1 ) ; return F [ i ] [ c_x ] [ c_y ] ; } int main ( ) { string S = " ( ( ) ) " ; int n = S . length ( ) ; memset ( F , -1 , sizeof ( F ) ) ; cout << noOfAssignments ( S , n , 0 , 0 , 0 ) ; return 0 ; }