C#で指定した個数の開き括弧・閉じ括弧のすべての有効な組み合わせを生成する方法

C#でバックトラッキング（バックトラック法）を利用すると、指定された個数の開き括弧「{」と閉じ括弧「}」からなるすべての有効な組み合わせを効率的に生成できます。

アルゴリズムの基本的な考え方

バックトラック用の再帰関数を作成し、次のルールに従って現在の文字列を更新していきます。

• 開き括弧を追加できる条件： まだ配置していない開き括弧が残っている場合（開き括弧の数がN未満）
• 閉じ括弧を追加できる条件： 閉じ括弧の数が開き括弧の数を上回らない場合（閉じ括弧の数が開き括弧の数より少ない）
• 終了条件： 現在の文字列の長さが2×Nに達した時点で、その文字列を1つの完成した組み合わせとして結果に出力する

このように、配置済みの括弧の数を記録しながら分岐をたどることで、「}{」のように閉じ括弧が先に来る無効な組み合わせを自動的に排除できます。

C#での実装例

以下は、N=2（括弧2組）の場合にすべての組み合わせを生成するC#のコード例です。

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace ConsoleApplication {
    public class BackTracking {
        public void Brackets() {
            char[] arr = new char[4];
            FindSequence(arr, 0, 2, 0, 0);
        }

        private static void FindSequence(char[] arr, int index, int N, int openBracket, int closeBracket) {
            // 閉じ括弧がN個並んだら、1つの組み合わせが完成
            if (closeBracket == N) {
                StringBuilder s = new StringBuilder();
                for (int i = 0; i < arr.Length; i++) {
                    s.Append(arr[i]);
                }
                Console.WriteLine(s);
                s = null;
                return;
            }
            else {
                // 開き括弧の方が多い場合は閉じ括弧を追加できる
                if (openBracket > closeBracket) {
                    arr[index] = '}';
                    FindSequence(arr, index + 1, N, openBracket, closeBracket + 1);
                }
                // 開き括弧がまだ残っている場合は開き括弧を追加できる
                if (openBracket < N) {
                    arr[index] = '{';
                    FindSequence(arr, index + 1, N, openBracket + 1, closeBracket);
                }
            }
        }
    }

    class Program {
        static void Main(string[] args) {
            BackTracking b = new BackTracking();
            b.Brackets();
        }
    }
}

実行結果

{}{}
{{}}

N=2の場合、「{}{}」と「{{}}」の2通りの有効な組み合わせが出力されます。なお、N組の括弧に対して生成される組み合わせの総数はカタラン数 C(2N, N)/(N+1) で表され、この手法の計算量は出力される組み合わせの数に比例して増加します。