括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

约定

• 有效括号组合要求：任意前缀中左括号数量不少于右括号数量，且左右括号总数相等。
• 返回的组合之间顺序任意，但每个组合本身是一个确定的字符串。
• n 的取值范围为 1 ≤ n ≤ 8。

输入

• n：括号对数

输出

所有有效括号组合组成的字符串数组。

示例一

输入：

n = 3

输出：

["((()))","(()())","(())()","()(())","()()()"]

示例二

输入：

n = 1

输出：

["()"]

示例三

输入：

n = 2

输出：

["(())","()()"]

复杂度要求

• 时间复杂度：O(4^n / sqrt(n))，即卡特兰数级别的输出规模
• 空间复杂度：O(n)，递归栈与路径存储