Given a number N, how do we generate all possible valid expressions with N pairs of brackets?
For example for N = 2, there are 2 such expressions
()()
(())
For N = 3, there are 5 expressions
((()))
(()())
(())()
()(())
()()()
We have a simple solution to this problem by using recursion. We design this method as follows.
For example for N = 2, there are 2 such expressions
()()
(())
For N = 3, there are 5 expressions
((()))
(()())
(())()
()(())
()()()
We have a simple solution to this problem by using recursion. We design this method as follows.
It takes two parameters left count, right count, buffer and an index. At each index we can either fill a left bracket or a right bracket.
As long as we have left brackets, we try to fill them and recursively call the method with one less left brace.
Then we check if we have more right braces than left braces, then fill it up with right brace. Recursively call the method with one less right brace.
When we don’t have any left or right braces remaining, we can print the contents of the buffer.
Here is the Java implementation.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Created by ravi on 6/23/15. | |
| */ | |
| public class GenerateParenthesis | |
| { | |
| public static void main(String [] args) | |
| { | |
| printBrackets(2); | |
| printBrackets(3); | |
| } | |
| public static void printBrackets(int n) | |
| { | |
| char [] exp = new char[2*n]; | |
| generateExp(n, n, exp, 0); | |
| } | |
| public static void generateExp(int left, int right, char []exp, int cnt) | |
| { | |
| //validation | |
| if( left < 0 || right < 0 || right < left ) | |
| return; | |
| if( left == 0 && right == 0 ) | |
| System.out.println(exp); | |
| else | |
| { | |
| if( left > 0 ) //As long as we have left parenthesis | |
| { | |
| exp[cnt] = '('; | |
| generateExp(left-1, right, exp, cnt+1); | |
| } | |
| if( right > left ) | |
| { | |
| exp[cnt] = ')'; | |
| generateExp(left, right-1, exp, cnt+1); | |
| } | |
| } | |
| } | |
| } |
by