题目背景

Special for beginners, ^_^

题目描述

给定一个整数 n，请用递归生成：

n 对括号组成的所有合法括号序列

并按字典序输出。

输入格式

一个整数

1 ≤ n ≤ 10

输出格式

输出所有合法括号序列，每行一个。

样例

3

((()))
(()())
(())()
()(())
()()()

样例解释

当 n = 3 时，共有 5 种合法括号组合。

合法的定义是：

任意前缀中 '(' 的数量 ≥ ')'

最终 '(' 和 ')' 数量相等