C++でn個の有効な括弧列（ブラケットシーケンス）を生成する方法

問題の概要

数値 n が与えられたとします。ここでいう括弧列（ブラケットシーケンス）とは、文字「(」と「)」のみから構成される文字列のことです。

さらに、有効な括弧列とは、元の文字同士の間に「1」と「+」を挿入することで、正しい算術式へと変換できる括弧列を指します。たとえば「()()」は「(1)+(1)」のように書き換えられるため、有効な括弧列であるといえます。

この記事では、数値 n が与えられたときに、長さ 2n の互いに異なる有効な括弧列をちょうど n 個見つけて出力する方法を解説します。

たとえば、入力が n = 4 の場合、出力は次のようになります。

["()()()()", "(())()()", "((()))()", "(((())))"]

解法のアイデア

この問題は、次のような規則的なパターンを利用することで簡単に解くことができます。

• k 番目（1 ≤ k ≤ n）の出力では、まず深さ k の完全に入れ子になった括弧「((...))」を出力します。
• その後、残りの部分を単純なペア「()」で埋めます。

この方法により、各行は必ず有効な括弧列となり、入れ子の深さが行ごとに異なるため、すべての行は互いに重複しない（ユニークな）文字列になります。

アルゴリズムの手順

以下の手順に従って解きます。

k を 1 から n まで繰り返す：
　　i を 1 から k まで繰り返し、「(」を出力
　　i を 1 から k まで繰り返し、「)」を出力
　　i を k + 1 から n まで繰り返し、「()」を出力
　　改行を出力

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void solve(int n) {
   for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= k; i++)
         cout << "(";
      for (int i = 1; i <= k; i++)
         cout << ")";
      for (int i = k + 1; i <= n; i++)
         cout << "()";
      cout << endl;
   }
}
int main() {
   int n = 4;
   solve(n);
}

入力

4

出力

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

計算量について

このアルゴリズムは、各括弧列の出力に O(n)、それを n 回繰り返すため、全体の時間計算量は O(n²) となります。非常にシンプルで効率的なアプローチであり、競技プログラミングでも十分に実用的です。