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

Мы уже делали пост об одной из самых заезженных задач — валидация скобочной последовательности. Эта задача у опытных собседуемых вызывает улыбку и желание сказать «hold my beer» интервьеру.

А вот вариация этой же самой задачи, где нужно сгенерировать все возможные валидные последовательности может загнать в ступор. Честно говоря, на практике я не сталкивался на собеседованиях с этой задачей, но, охотно верю, что ее могут практиковать вместо классической валидации (@avivasyuta несколько раз сталкивался 😀). Подобный трюк может выбить из колеи и заставить обеседуемого идти не по заученной формуле, а изобретать решение из головы.

Хорошая новость — у задачи очень понятный брутфорс с фоллбеком - мы можем сперва просто нагенерить все возможные строки из скобок, а потом провалидировать их :). Даже если в стрессовой ситуации вы не придумаете ничего другого, вы покажите, что умеете оптимально валидировать :).

Но, можно немного улучшить решение.

Сложность: 🟠 Cредняя

ℹ️ Описание

Дано целое неотрицательное число n. Напшите функцию, которая сгенерирует все возможные варианты правильных скобочных последовательностей длиной 2n, состоящих из круглых скобок — «(» и «)».

⚠️ Ограничения

🔹Количество пар скобок от 1 до 8
🔹Допустимые символы в строках - «(» и «)».

1️⃣ Пример

Входящие данные: 3

Ответ: ["((()))","(()())","(())()","()(())","()()()"]

2️⃣ Пример

Входящие данные: 1

Ответ: ["()"]

✅ Решение

Суть оптимального решения — отбрасывать невалидные строки на моменте генерации. Задача сильно упрощается тем фактом, что нам нужно использовать только один тип скобок, поэтому мы можем воспользоваться счетчиками открытых/закрытых скобок (хотя, кажется, если в решении мы заменим счетчики на стек и немного модифицируем, то мы сможем генерировать последовательности и для n видов скобок).

Мы можем выделить несколько правил:
🔹 Любая строка должна начинаться с открывающей скобки
🔹 Количество открытых и закрытых скобок должно быть равно n
🔹 Количество закрывающих скобок в любой итерации не должно превышать количество открывающих

Исходя из этих правил легко написать рекурсивную функцию по генерации.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени
В данной задачи мы генерируем m строк длиной 2*n. На любой позиции строки может быть один из двух символов. Если предположить, что символы ставятся независимо друг от друга и вспомнить простенькую формулу из комбинаторики, то m = 2^(2*n-1).
В нашем оптимальном решениии символы зависят друг от друга, так что диапазон возможных решений сильно снижается. Но, думаю, на интервью будет валидно сказать, что сложность сравнима с O(2^(2*n-1)).

По памяти
Нам нужно выделить память для хранения всех результирующих строк. Каждая строка имеет длину 2*n. Также как и в случае сложности, валидно будет сказать, что кол-во строк сравнимо с O(2^(2*n-1)).
Таким образом, оценка по памяти сравнима с O(n*2^(2*n-1)).


#strings #arrays #medium