C++: вывести все корректные комбинации пар круглых скобок

В отличие от проверки правильности расстановок скобок в строке, здесь мы выводим все возможные комбинации корректной расстановки скобок.

Вывести все корректные комбинации пар круглых скобок, которые можно сформировать из n пар скобок, которые закрываются и открываются.

Что любопытно, зависимость количества расстановок от количества пар скобок n даёт типичные числа Каталана, они же A000108.

Проверено в консоли Visual Studio 2015.

#include <iostream>
using namespace std;

#define MAX_SIZE 256 /* используем просто статический буфер */

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

int main() {
 int n = 10;
 bracketir(0,n,0,0);  //брекетир - это такой маленький рэкетир с брекетами
 cin.get(); return 0;
}

28.02.2018, 12:58 [2596 просмотров]