Generate Parentheses

 Given an integer 'n'. Print all the possible pairs of 'n' balanced parentheses.

The output strings should be printed in the sorted order considering '(' has higher value than ')'.

Input Format

Single line containing an integral value 'n'.

Constraints

1<=n<=11

Output Format

Print the balanced parentheses strings with every possible solution on new line.

Sample Input

2

Sample Output

()() (())

import java.util.Scanner;
public class GenerateParentensis
{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
int num=s.nextInt();
generateParenthensis(num,0,0,"");
s.close();
}
private static void generateParenthensis

(int num,int opening,int closing,String ans)
{
if(opening==num && closing==num)
{
System.out.println(ans);
return;
}
if(opening<num)
{
generateParenthensis(num, opening+1, closing, ans+"(");
}
if(closing<opening)
{
generateParenthensis(num, opening, closing+1, ans+")");
}
}

}