はじめに
最近競プロを始めたので，競プロ典型90問の★1~★3を解いて典型問題へのアプローチ方法を学んでいます．
公式のソースコードがC++で困っているPython勢の方も多いと思うので, 自分の解答をシェアしたいと思います！
初心者の解答なので，もっといい方法があれば教えていただけると嬉しいです！
002 Encyclopedia of Parentheses（★3）
問題文
長さ $N$ の正しいカッコ列をすべて、辞書順に出力してください。
ただし、正しいカッコ列は次のように定義されています :
-
()は正しいカッコ列である - $S$ が正しいカッコ列であるとき、文字列
($+S+$)は正しいカッコ列である - $S,T$ が正しいカッコ列であるとき、文字列 $S+T$ は正しいカッコ列である
- それ以外の文字列はすべて、正しいカッコ列でない
例えば、
()()(()())(())()()()()()()()()
は正しいカッコ列ですが、
)()))()(((((((a))))
は正しいカッコ列ではありません。
また、 ( の方が ) よりも辞書順で早いものとします。
制約
- $1≤N≤20$
- $N$ は整数
解法
制約を見ると $N$ が極端に小さいので，全探索ができそうだと考えられます．さらに，正しいカッコ列に含まれるのは ( と ) の2種類だけなので，bit全探索を使えばよさそうだと気づくと思います．
すなわち，( または ) を $N$ 個つなげてできるすべてのカッコ列に対して，それが正しいカッコ列かどうかを判定して条件を満たすものだけをリストに入れるようにします．
ここで，$N$ が奇数の場合については正しいカッコ列が存在しないことが明らかなので，これ以降は $N$ が偶数の場合のみを考えることにします．
判定の仕方については，( の個数と ) の個数の差を記録するための変数 cnt を用意して，カッコ列の先頭から順に見ていき ( であれば cnt を1増やし，) であれば1減らすことにします．
そして，最後に cnt を更新した時点で cnt = 0 であれば正しいカッコ列であり，途中で cnt < 0 になったり，最後に cnt を更新した時点で cnt ≠ 0 になったりした場合は正しいカッコ列ではないということになります．
ここまでできれば，あとはリストを昇順にソートして出力することで辞書順に出力されます．
これによって，$O(N2^N)$ の計算量で解くことができます．
↓↓↓ bit全探索の解説はこの記事がわかりやすくてオススメです ↓↓↓
実装
Pythonでbit全探索を行う際に使えるモジュールとして itretools.product があります．これは競プロをしているとよく使うモジュールだと思うので，使い方を覚えておくと良いと思います．
itertools には product 以外にも便利な関数が用意されているので，公式リファレンスを確認してみてください．
from itertools import product
import sys
input = sys.stdin.readline
# 文字列sとその長さnを受け取って正しいカッコ列かどうかを判定する関数
def judge(s, n):
cnt = 0
for i in range(n):
if p[i] == '(':
cnt += 1
else:
if cnt > 0:
cnt -= 1
else:
return False
if cnt != 0:
return False
return True
N = int(input())
# Nが奇数の場合は正しいカッコ列は存在しないため考えない
if N % 2 == 0:
ans = []
# 長さNのカッコ列を全探索
for p in product('()', repeat=N):
if judge(p, N):
# 正しいカッコ列の条件を満たしていればansに追加
ans.append(p)
# 辞書順にソート
ans.sort()
# 出力
for i in range(len(ans)):
print(*ans[i], sep='')
さいごに
今回のように $N\leq20$ 程度であれば指数オーダーでも十分間に合うため，bit全探索を使うとうまくいく場合が多いと思います．
よく分からないことやコードの改善点などありましたら，気軽にコメントしてください．
最後までお付き合いいただきありがとうございました！