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

Задача

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

1. (())
2. ()()

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

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

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

        cur_seq[cur_index] = ')';
        cur_balance--;

    } else {
        // пробуем поставить обе скобки, сначала ставим ту,
        // которая лексикографически меньше

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

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