1663. Скобочные последовательности

Дано целое число n (1 ≤ n ≤ 10). Выведите в алфавитном порядке все правильные скобочные последовательности длины 2n, полагая, что символ '(' в алфавите идет раньше чем ')'.

Правильная скобочная последовательность – это либо пустая строка, либо строка вида (S), где S – правильная скобочная последовательность, либо строка вида S₁S₂, где S₁ и S₂ – правильные скобочные последовательности.

Вход. Одно целое число n (0 ≤ n ≤ 10).

Выход. Выведите в алфавитном порядке все правильные скобочные последовательности длины 2n, по одной последовательности в строке, без пробелов.

Пример входа	Пример выхода
3	((())) (()()) (())() ()(()) ()()()

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Задачу будем решать полным перебором. Пусть s – строка, в которой будем генерировать требуемые последовательности. Изначально она пустая. Пусть переменные left и right содержат количество еще не использованных открытых и закытых скобок соответственно (изначально left = right = n). Далее:

· Если left > 0, то к строке s можно приписать ‘(‘.

· Если left < right, то к строке s можно приписать ‘)‘. Количество уже использованных открытых скобок не должно быть меньше числа закрытых.

При left = right = 0 выводим очередную правильную скобочную последовательность.

Реализация алгоритма

Функция gen генерирует последовательности. Часть уже сгенерированной скобочной последовательности содержится в строке s. Переменные left и right содержат количество еще не использованных открытых и закрытых скобок соответственно.

void gen(string s, int left, int right)

{

if (left == 0 && right == 0)

{

cout << s << endl;

return;

}

if (left > 0) gen(s + "(", left - 1, right);

if (left < right) gen(s + ")", left, right - 1);

}

Основная часть программы. Читаем значение n и запускаем генерацию скобочных последовательностей.

cin >> n;

gen("",n,n);