典型90問002[bit全探索][カッコ列]

002 - Encyclopedia of Parentheses（★3）

　大変お久しぶりです．死ぬほど忙しかった修士1年の前期が終わり余裕が出来たので久々に競プロを再開して行きたいと思います．M1前期は就活や授業，研究，学会とてんこもりでしたのでまた機会があったら振り替えっていきたいと思います．

　友人(tukasくん)に過去問もいいけど典型90問も良いよと進められたのでしばらくは★3以下を解いて入茶を目指していきます．

■方針

"("と")"の2パターンの並び替えなのでbit全探索を用いることには気づけましたが，カッコ列の正誤判定がわからず諦めてしまいました．ggったところカッコ列は競プロの典型のようで，以下のけいちょんさんのブログが大変分かりやすかったです．記事を読んで納得できました．

競プロ典型 90 問 002 - Encyclopedia of Parentheses（★3） - けんちょんの競プロ精進記録

■コード

N = int(input())

from itertools import product
def isvalid(S):
   score = 0
   for c in S:
       if c == '(':
           score += 1
       else:
           score -= 1

       # 途中で 0 を下回るとダメ
       if score < 0:
           return False

   # 最後に 0 なら True、そうでなければ False
   return (score == 0)

for bit in product(["(",")"], repeat = N):
 if (isvalid(bit)):
       # リストを文字列に
       print(*bit, sep='')