Generate All Valid Parentheses
Given an integer n, generate all strings with n matching parentheses.
"matching" parentheses mean
- there is equal number of opening and closing parentheses.
- each opening parenthesis has matching closing parentheses.
For example, () is a valid string but )( is not a valid string because ) has no matching parenthesis before it and ( has no matching parenthesis after it.
Input & Output
Input
n — number of matching parentheses
Output
all valid strings with n matching parentheses
Example
Input
n = 2
Output
(()) ()()
Explanation
There are two ways to create a string with 2 matching parentheses.
Example
Input
n = 3
Output
((())) (()()) (())() ()(()) ()()()
Explanation
There are 5 ways to create a string with 3 matching parentheses.