バランスの取れた括弧のすべての組み合わせをC++で印刷します

この問題では、整数nが与えられます。私たちのタスクは、n個のバランスの取れた括弧の可能なすべてのペアを印刷することです。

バランスのとれた括弧 対応するすべての開始記号の終了記号を持つ括弧のペアです。また、ペアは適切にネストする必要があります。

問題を理解するために例を見てみましょう

Input: n = 2
Output: {}{} {{}}

この問題を解決するには、ブラケットのペアを追跡する必要があります。ブラケットの初期カウントは0です。次に、ブラケットの総数がn未満になるまで、関数を再帰的に実行します。角かっこを数えます。数に基づいて角かっこを再帰的に呼び出します。開始ブラケットの数が終了よりも多い場合は、終了ブラケットを配置してから、残りのペアの数を調べます。開始ブラケットがn未満の場合は、残りのブラケットのペアを再帰的に呼び出します。

例

以下のコードは、ソリューションの実装を示しています

# 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 −
{}{}{}
{}{{}}
{{}}{}
{{}{}}
{{{}}}