Генерация всех правильных скобочных последовательностей: различия между версиями
Материал из Algocode wiki
Строка 42: | Строка 42: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | {{Автор|Александр Гришутин|rationalex}} |
Версия 11:39, 22 февраля 2020
Задача
По данному $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);
}
}
}
}
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex