C++でバランスの取れた括弧の組み合わせをすべて出力する方法

この記事では、整数 n が与えられたときに、n組のバランスの取れた括弧のすべての組み合わせを出力する問題をC++で解く方法を解説します。

バランスの取れた括弧とは？

バランスの取れた括弧とは、すべての開き括弧「{」に対して対応する閉じ括弧「}」が存在し、かつ括弧が正しく入れ子（ネスト）になっている文字列のことです。例えば「{{}}」はバランスが取れていますが、「}{{」のように対応関係が崩れている文字列は不正となります。

問題例

具体例を見てみましょう。

入力：n = 2
出力：{}{} {{}}

解法のアプローチ

この問題を解くには、開き括弧と閉じ括弧の数を常に追跡しながら、再帰的に文字列を構築していきます。基本的な考え方は次の通りです。

• 開き括弧と閉じ括弧のカウントを初期値 0 とする。
• 閉じ括弧の数が n に達した時点で、その文字列を完成形として出力する。
• 開き括弧の数が閉じ括弧より多い場合は、閉じ括弧を追加できる。
• 開き括弧の数が n 未満の場合は、新たに開き括弧を追加できる。
• 上記の条件をもとに再帰呼び出しを行い、すべての組み合わせを網羅的に生成する。

C++での実装例

以下のコードは、この解法を実装したものです。

#include <iostream>
using namespace std;
#define MAX_COUNT 100

void printParenthesesPairs(int pos, int n, int open, int close){
    static char str[MAX_COUNT];
    if(close == n) {
        cout<<str<<endl;
        return;
    }
    else {
        if(open > close) {
            str[pos] = '}';
            printParenthesesPairs(pos+1, n, open, close+1);
        }
        if(open < n) {
            str[pos] = '{';
            printParenthesesPairs(pos+1, n, open+1, close);
        }
    }
}

int main() {
    int n = 3;
    cout<<"All parentheses pairs of length "<<n<<" are:\n";
    if(n > 0)
        printParenthesesPairs(0, n, 0, 0);
    getchar();
    return 0;
}

実行結果

All parentheses pairs of length 3 are −
{}{}{}
{}{{}}
{{}}{}
{{}{}}
{{{}}}

計算量について

n組のバランスの取れた括弧の総数はカタラン数 Cₙ = (2n)! / ((n+1)! × n!) で表され、プログラムが出力する文字列の個数はこれと一致します。したがって、このアルゴリズムの時間計算量はおおよそ O(4ⁿ / √n) となり、nが大きくなると組み合わせの数は急激に増加することに注意が必要です。