Generate Parentheses

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Examples

Example 1:

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Example 3:

Input: n = 2
Output: ["(())", "()()"]

Constraints

• 1 <= n <= 8

Expected Complexity

• Time: O(4^n / sqrt(n)). the nth Catalan number
• Space: O(n). recursion depth