ISourceCode

Make the frequent cases fast and the rare case correct

Catalan Numbers – Combinatorial Problem – Print all valid properly opened and closed combination of n-pairs of parentheses

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
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: