Find the number of valid parentheses expressions of given length | Java program to find valid paranthesisations of length n The majority of code is taken from method 3 of https : www . geeksforgeeks . org / program - nth - catalan - number / ; Returns value of Binomial Coefficient C ( n , k ) ; Since C ( n , k ) = C ( n , n - k ) ; Calculate value of [ n * ( n - 1 ) * -- - * ( n - k + 1 ) ] / [ k * ( k - 1 ) * -- - * 1 ] ; A Binomial coefficient based function to find nth catalan number in O ( n ) time ; Calculate value of 2 nCn ; return 2 nCn / ( n + 1 ) ; Function to find possible ways to put balanced parenthesis in an expression of length n ; If n is odd , not possible to create any valid parentheses ; Otherwise return n / 2 'th Catalan Number ; Driver program to test above functions
class GFG { static long binomialCoeff ( int n , int k ) { long res = 1 ; if ( k > n - k ) k = n - k ; for ( int i = 0 ; i < k ; ++ i ) { res *= ( n - i ) ; res /= ( i + 1 ) ; } return res ; } static long catalan ( int n ) { long c = binomialCoeff ( 2 * n , n ) ; return c / ( n + 1 ) ; } static long findWays ( int n ) { if ( ( n & 1 ) != 0 ) return 0 ; return catalan ( n / 2 ) ; } public static void main ( String [ ] args ) { int n = 6 ; System . out . println ( " Total ▁ possible ▁ expressions ▁ of ▁ length ▁ " + n + " ▁ is ▁ " + findWays ( 6 ) ) ; } }