Given a positive integer n, return ALL strings of length 2*n with well formed round brackets.

Example

Input: 3

Output:

[

    "((()))",

    "(()())",

    "(())()",

    "()(())",

    "()()()"

]

Any array containing these five strings in any order is a correct output.

Notes

Input Parameters: Function has one argument, integer n.

Output Format: Return array of strings containing all possible well formed round brackets string of length 2*n. Order of strings in the returned array is insignificant, e.g. for n=2 both ["(())", "()()"] and ["()()", "(())"] will be accepted.

Constraints:

• 1

• Only use round brackets. '(' and ')'.

Solution

There are many possible solutions for this problem. Have a look at the solution provided by us.

Time Complexity:

O(2n * catalan number(n)).

Auxiliary Space Used:

O(2n * catalan number(n)).

Space Complexity:

O(2n * catalan number(n)).