In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894). – Wikipedia

The nth Catalan number is given directly in terms of binomial coefficients by

The first Catalan numbers (sequence A000108 in OEIS) for n = 0, 1, 2, 3, … are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

How many ways are there to build a balanced formula from n sets of left and right parentheses? For example, there are five ways to do it for n = 3: ((())), ()(()), (())(), (()()), and ()()(). The leftmost parenthesis l matches some right parenthesis r, which must partition the formula into two balanced pieces, the part between l and r, and the part to the right of r. If the left part contains k pairs, the right part must contain n − k − 1 pairs, since l,r represent one pair.

Both of these sub formulas must be well formed, which leads to the recurrence given above – Programming challenges

Implementation:

import java.util.Scanner;
public class Parentheses{
static void ParCheck(int left,int right,String str)
{
if (left == 0 && right == 0)
{
System.out.println(str);
}
if (left > 0)
{
ParCheck(left-1, right+1 , str + "(");
}
if (right > 0)
{
ParCheck(left, right-1, str + ")");
}
}
public static void main(String[] args)
{
Scanner input=new Scanner(System.in);
System.out.println("Enter the number");
int num=input.nextInt();
String str="";
ParCheck(num,0,str);
}
}

OUTPUT:

labuser@ubuntu:~$ java Parentheses

Enter the number

3

((()))

(()())

(())()

()(())

()()()

labuser@ubuntu:~$ java Parentheses

Enter the number

4

(((())))

((()()))

((())())

((()))()

(()(()))

(()()())

(()())()

(())(())

(())()()

()((()))

()(()())

()(())()

()()(())

()()()()

### Like this:

Like Loading...

*Related*