002 - Encyclopedia of Parentheses(★3)
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 3 点
問題文
長さ N の正しいカッコ列をすべて、辞書順に出力してください。
ただし、正しいカッコ列は次のように定義されています :
()
は正しいカッコ列である- S が正しいカッコ列であるとき、文字列
(
+S+)
は正しいカッコ列である - S,T が正しいカッコ列であるとき、文字列 S+T は正しいカッコ列である
- それ以外の文字列はすべて、正しいカッコ列でない
例えば、
()()
(()())(())
()()()()()()()()
は正しいカッコ列ですが、
)(
)))()(((
((((a))))
は正しいカッコ列ではありません。
また、 (
の方が )
よりも辞書順で早いものとします。
制約
- 1 \leq N \leq 20
- N は整数
入力
入力は以下の形式で標準入力から与えられます。
N
出力
長さ N の正しいカッコ列をすべて、辞書順に、改行区切りで出力してください。
入力例 1
2
出力例 1
()
長さ 2 の正しいカッコ列は ()
のみです。
入力例 2
3
出力例 2
※何も出力しない場合もあります。
入力例 3
4
出力例 3
(()) ()()
入力例 4
10
出力例 4
((((())))) (((()()))) (((())())) (((()))()) (((())))() ((()(()))) ((()()())) ((()())()) ((()()))() ((())(())) ((())()()) ((())())() ((()))(()) ((()))()() (()((()))) (()(()())) (()(())()) (()(()))() (()()(())) (()()()()) (()()())() (()())(()) (()())()() (())((())) (())(()()) (())(())() (())()(()) (())()()() ()(((()))) ()((()())) ()((())()) ()((()))() ()(()(())) ()(()()()) ()(()())() ()(())(()) ()(())()() ()()((())) ()()(()()) ()()(())() ()()()(()) ()()()()()