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