JavaScriptでn組の括弧をバランスよく組み合わせる全パターンを生成する方法

問題

数値 n を引数として受け取るJavaScript関数を作成する必要があります。この関数は、n組の丸括弧「(」「)」を正しくバランスさせた文字列のパターンをすべて含む配列を返します。

例えば、n = 3 の場合の出力は次のとおりです。

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

アルゴリズムの考え方

この問題は、再帰呼び出し（バックトラッキング）を使うことで効率的に解くことができます。ポイントは、次の2つの変数で状態を管理することです。

• left：まだ配置していない開き括弧「(」の残り個数
• right：現在ペア未確定の開き括弧に対応する、閉じ括弧「)」を配置できる個数

「(」を1つ追加すると left が1減り、代わりに right が1増えます。一方、「)」を追加できるのは right が0より大きい場合だけです。そして、left と right が両方とも0になった時点で、1つの完全なバランス文字列が完成したことになります。

実装例

以下が実際のコードです。

const res = [];
const buildcombination = (left, right, str) => {
    if (left === 0 && right === 0) {
        res.push(str);
    }
    if (left > 0) {
        buildcombination(left-1, right+1, str+"(");
    }
    if (right > 0) {
        buildcombination(left, right-1, str+")");
    }
}
buildcombination(3, 0, "");
console.log(res);

出力結果

コンソールには以下のように表示されます。

[ '((()))', '(()())', '(())()', '()(())', '()()()' ]

生成された5つのパターンは、いずれも開き括弧と閉じ括弧の数が等しく、文字列のどの時点を見ても閉じ括弧の数が開き括弧を超えることがない、正しくバランスの取れた文字列になっています。