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

  • n: number of matching parentheses

Output

all valid strings with n matching parentheses

Examples

Example 1:

Input:

1n = 2

Output: (()) ()()

Explanation:

There are two ways to create a string with 2 matching parentheses.

Example 2:

Input:

1n = 3

Output: ((())) (()()) (())() ()(()) ()()()

Explanation:

There are 5 ways to create a string with 3 matching parentheses.

Try it yourself

Solution

←
↑TA πŸ‘¨β€πŸ«