Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

Objec­tive: Given “n”, generate all valid parenthesis strings of length “2n”.
Example:

Given n=2

Output:
(())
()()

Approach:

  • Recursion is the key here.
  • Divide the N into N/2 and N/2 (Count for open and closed parentheses ).
  • Select the open parentheses, add it to the result string and reduce its count and make a recursive call.
  • Select the close parentheses, add it to the result string and reduce its count and make a recursive call.
  • To print only valid parentheses, make sure at any given point of time, close parentheses count is not less that open parentheses count because it means close parentheses has been printed with its respective open parentheses.
  • See picture for better explanation.

Generate all valid parenthesis strings of length 2n of given n

Code:

public class PrintValidParentheses {
public static void Validparentheses(int openP, int closeP, String string) {
if (openP == 0 && closeP == 0) // mean all opening and closing in
// string,
// print it
System.out.println(string);
if (openP > closeP) // means closing parentheses is more than open ones
return;
if (openP > 0)
Validparentheses(openP 1, closeP, string + "("); // put ( and
// reduce
// the count by
// 1
if (closeP > 0)
Validparentheses(openP, closeP 1, string + ")"); // put ) and
// reduce
// the count by
// 1
}
public static void printParentheses(int n) {
Validparentheses(n / 2, n / 2, "");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int n = 4;
printParentheses(n);
}
}


Output:

(())
()()