Скобочные последовательности

Правильная скобочная последовательность (ПСП) определяется рекурсивно: пустая строка — ПСП; если $A$ — ПСП, то (A) — ПСП; если $A$ и $B$ — ПСП, то $AB$ — ПСП.

Из определения не сразу видно, как их перебирать и считать. Есть два взгляда, и оба нужны.

Взгляд первый: баланс

Пойдём по строке, прибавляя единицу на открывающей скобке и вычитая на закрывающей.

Строка правильная тогда и только тогда, когда баланс нигде не отрицателен и равен нулю в конце.

Это полный критерий, и проверяется он одним проходом:

int balance = 0;
for (char c : s) {
    balance += (c == '(') ? 1 : -1;
    if (balance < 0) return false;
}
return balance == 0;

Отрицательный баланс означает, что закрывающих скобок уже больше, чем открывающих, — такую строку не спасти ничем дальше.

Генерация

Из критерия сразу получается перебор с отсечениями:

void generate(int placed, int balance) {
    if (placed == 2 * n) { if (balance == 0) print(prefix); return; }
    if (balance + 1 <= 2 * n - placed - 1) {   // хватит ли места закрыть
        prefix += '(';
        generate(placed + 1, balance + 1);
        prefix.pop_back();
    }
    if (balance > 0) {                         // есть что закрывать
        prefix += ')';
        generate(placed + 1, balance - 1);
        prefix.pop_back();
    }
}

Первое отсечение: если открыть скобку, баланс станет balance + 1, и на её закрытие нужно столько же символов, сколько осталось. Второе: закрыть нечего, если баланс нулевой.

С этими условиями перебор заходит только в вершины, из которых достижима хотя бы одна ПСП, — то есть выводит ровно то, что нужно, и ничего лишнего.

Порядок вывода лексикографический, если ( перебирается раньше ). Поменяете ветки местами — получите обратный порядок и «неверный ответ» на задаче, где просили лексикографический.

Несколько видов скобок

Когда скобки круглые и квадратные, одного числа мало: важно, какая именно скобка ждёт закрытия. Тогда вместо баланса ведут стек открытых скобок.

Закрывающую скобку можно поставить, только если она соответствует вершине стека. Открывающую — всегда, пока хватает места.

void generate(int placed) {
    if (placed == length) { if (st.empty()) print(prefix); return; }
    for (char open : {'(', '['}) {              // открывающие: всегда можно
        if ((int)st.size() + 1 > length - placed - 1) continue;
        st.push_back(open); prefix += open;
        generate(placed + 1);
        prefix.pop_back(); st.pop_back();
    }
    if (!st.empty()) {                            // закрывающая: только парная
        char open = st.back();
        char close = (open == '(') ? ')' : ']';
        st.pop_back(); prefix += close;
        generate(placed + 1);
        prefix.pop_back(); st.push_back(open);
    }
}

Тот же стек — стандартная проверка правильности такой строки: открывающие кладём, на закрывающей сверяем с вершиной и снимаем; в конце стек обязан быть пуст.

Проверено против полного перебора всех строк из четырёх символов: множество выданного совпадает для всех длин до десяти. Количество последовательностей длины $2n$ равно $C_n \cdot 2^n$ — каждой паре независимо выбирается вид скобки: 2, 8, 40, 224, 1344 для $n$ от 1 до 5.

Про порядок здесь стоит быть внимательнее: код выдаёт сначала все варианты с открывающей скобкой, потом с закрывающей, а это не порядок ASCII — там ) идёт раньше [. Если условие требует именно ASCII-порядок, ветки нужно переставить под него.

Взгляд второй: рекурсивное разложение

Когда нужно количество, а не сами строки, перебор не годится: последовательностей экспоненциально много.

Вернёмся к определению. Любая непустая ПСП однозначно раскладывается так: первая скобка с её парой, внутри — какая-то ПСП, после — какая-то ПСП.

Если внутри $2k$ символов, то снаружи остаётся $2(i - k - 1)$. Перебирая $k$, получаем

$$dp_i = \sum_{k=0}^{i-1} dp_k \cdot dp_{i-k-1}, \qquad dp_0 = 1$$

vector<long long> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; i++)
    for (int k = 0; k < i; k++)
        dp[i] += dp[k] * dp[i - k - 1];

Это числа Каталана. Проверено: количество ПСП, найденное перебором, совпадает с этой формулой для всех $n \le 10$; $C_{10} = 16\,796$.

Сложность — $O(n^2)$, чего хватает при $n$ до нескольких тысяч. Есть и замкнутая формула $C_n = \frac{1}{n+1}\binom{2n}{n}$, считаемая по модулю за логарифм.

Где ещё встречаются числа Каталана

Одна и та же последовательность $1, 1, 2, 5, 14, 42, 132, \dots$ считает:

• правильные скобочные последовательности из $n$ пар;
• бинарные деревья с $n$ вершинами;
• триангуляции выпуклого $(n+2)$-угольника;
• пути из $(0,0)$ в $(n,n)$ по сетке, не поднимающиеся выше диагонали;
• способы расставить скобки в произведении $n+1$ множителя.

Совпадение не случайное: между всеми этими объектами есть явные взаимно однозначные соответствия. Практическая польза прямая — узнав в ответе числа Каталана, вы часто узнаёте и способ решения: свести задачу к скобкам и применить то, что уже известно про них.

И обратное: если первые несколько ответов у вас получились 1, 2, 5, 14 — почти наверняка это Каталан, и стоит проверить гипотезу до того, как писать сложный перебор.