Генерация всех правильных скобочных последовательностей
Материал из Algocode wiki
Версия от 10:47, 22 февраля 2020; Rationalex (обсуждение | вклад)
Задача
По данному $n$ надо вывести все правильные скобочные последовательности из $n$ пар скобок в лексикографическом порядке. Например, если $n = 2$, надо вывести
- (())
- ()()
Рекурсивный перебор
Давайте напишем следующую процедуру
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);
}
}
}
}