競プロ典型90問 002 - Encyclopedia of Parentheses - Qiita

問題 競プロ典型90問 002 Encyclopedia of Parentheses 解法 以下の2つを主に考えてコードを書きました。 再起関数を使い長さNになるまで文字を追加していく。 正しいカッコ列の条件を外れた場合、文字を追加しない。 正しいカッコ列の条件 まず、正しいカッコ列の条件を考えたところ、以下の2つになりました。 カッコ列を左から見て行った時に")"の数が"("を超えないこと。 カッコ列の"("の数と")"の数が等しいこと。 ここで長さNのカッコ列を全探索して、全てにおいて上記の判定をしても良いのですが、大変そうだなぁと思ったのでもう少し考えてみました。 2の条件から以下の2つがわかります。 Nが奇数の場合正しいカッコ列は存在しないこと。 カッコ列を左から見て行った時に"("の数がN//2を超えないこと。 ということで、空の文字列から1文字ずつ追加してカッコ列を作る際に、