Генерация всех правильных скобочных последовательностей

Задача

По данному $n$ надо вывести все правильные скобочные последовательности из $n$ пар скобок в лексикографическом порядке. Например, если $n = 3$, надо вывести

1. ((()))
2. (()())
3. (())()
4. ()(())
5. ()()()

Рекурсивный перебор

Давайте напишем следующую процедуру

void gen(int n, vector<char>& cur_seq, int cur_balance=0, int cur_index=0) {
  if (cur_index == 2 * n) {
    for (auto& bracket : cur_seq) {
       cout << bracket;
    }
    cout << endl;
  } else {
    if (cur_balance == 2 * n - cur_index) {
        // если количество оставшихся позиций в точности равно
        // количеству скобок, которые надо закрыть, то новые скобки мы не можем открывать

        cur_seq[cur_index] = ')';
        cur_balance--;
        gen(n, cur_seq, cur_balance, cur_index + 1);
    } else {
        // пробуем поставить обе скобки, сначала ставим ту,
        // которая лексикографически меньше

        cur_seq[cur_index] = '(';
        cur_balance++;
        gen(n, cur_seq, cur_balance, cur_index + 1);

        if (cur_balance > 1) {
            cur_seq[cur_index] = ')';
            cur_balance -= 2;
            gen(n, cur_seq, cur_balance, cur_index + 1);
       }
    }
  }
}

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex