Atcoder 競プロ典型 90 問 002 - Encyclopedia of Parentheses（★3）

問題のリンクatcoder.jp

・長さNの条件を満たす括弧列を辞書順に全て出力する問題

正しい例

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

正しくない例

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

考えたこと

• "(" と ")" はセットであるからNは偶数でないといけない
• ")" が先に来てはいけないため、集計変数valを用意し、 "(" を+1 ")" を-1とおき加算していくループを回すと良いかも
• ループの途中でvalが負になると終了し、出力しない

解法

N = int(input())

# 10 や 1010、1100などが出力されるが、
# bit全数探索をする。辞書順にするため2^Nから1ずつ減らし、2^(N-1)-1まで
for bit in range(2**N,2**(N-1)-1, -1):
  # 集計変数を用意
  val = 0
  ans = []
  for i in range(N-1, -1, -1):
    if bit & (1 << i):
      val += 1
      ans.append('(')
    else:
      val -= 1
      ans.append(')')
    if val < 0:
      break
  
  if val == 0:
    # リストの値を隙間をなく出力
    print(*ans,sep='')    

他の方のコードを見たらbit 全探索は itertools.product を使うと良いとわかったためコードを改良する。

from itertools import product

N = int(input())

# ( と ) で長さがNの組み合わせを全てループする
for S in product(['(', ')'], repeat=N):
    val = 0
    for c in S:
        if c == '(':
            val += 1
        else:
            val -= 1

        if score < 0:
            break

    if score == 0:
        # リストの値を隙間をなく出力
        print(*S, sep='')