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.

n: number of matching parentheses

all valid strings with n matching parentheses

n = 2

Output: (()) ()()

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

n = 3

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

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