このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。
問題
002 - Encyclopedia of Parentheses（★3）
ポイント
長さがNとなる「(」と「)」の組み合わせを全て試し、正しいカッコ列かどうかを検証します。
Pythonで組み合わせを生成するにはitertoolsのcombinationsを使用すると便利です。
正しいカッコ列かどうかを検証するには「(」を1、「)」を-1としてカッコ列の左から順番に加算していきます。正しいカッコ列ではない条件は以下の2つです。
①途中で-1となる
例：()())( ※左から加算していくと1→0→1→0→-1→0 となります。
②最後まで加算したときに0になっていない
例：()(())( ※左から加算していくと1→0→1→2→1→0→1 となります。
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
import itertools
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N = int(input())
comb = list(itertools.product(['(', ')'], repeat=N)) # 組み合わせの生成
ans = []
for c in comb:
cnt = 0
for i in range(len(c)):
if c[i] == '(':
cnt += 1
else:
cnt -= 1
if cnt == -1: # 途中で-1となれば正しいカッコ列ではない
break
else:
if cnt == 0: # 最後まで加算したときに0になっていれば正しいカッコ列
ans.append(c)
print(*[''.join(a) for a in ans], sep='\n')
if __name__ == '__main__':
main()
