Generate Parentheses

Q: Какова временная сложность Generate Parentheses?

Решение с возвратом выводит числа Каталана C(n) = (2n)! / ((n+1)! n!) строк, количество которых растёт как 4^n / (n^1.5 √π) . Длина каждой строки равна 2n , и поиск не тратит время на бесперспективные ветви, поэтому общее время составляет O(4^n / √n) . Дополнительная память составляет O(n) для текущей строки и стека вызовов, не считая вывода.

Q: Сколько существует корректных скобочных последовательностей для n пар?

Точно n-е число Каталана: 1, 2, 5, 14, 42, 132, 429 и 1,430 для n от 1 до 8. Это можно увидеть так: каждая правильно сформированная строка имеет вид ( + A + ) + B, где первая ( соответствует этой ) , а A и B правильно сформированы и вместе содержат n-1 пар. Суммирование по размеру A даёт рекуррентное соотношение для чисел Каталана.

Q: Почему условие closed < opened гарантирует корректную строку?

Строка становится некорректной, когда символ ) встречается без незакрытой ( перед ним, то есть когда количество ) превысило бы количество ( . Если разрешать ) только при условии closed < opened , этого никогда не произойдёт, а если разрешать ( только при условии opened < n , оба счётчика достигнут n при длине 2n . Вместе эти два правила описывают каждый префикс правильно сформированной строки.

Q: Можно ли решить задачу Generate Parentheses без рекурсии?

Да. Храни стек частичных состояний, каждое из которых представляет собой строку с двумя счётчиками, и расширяй состояние по тем же двум правилам. Если добавить в стек расширение ) перед расширением ( , то первым извлекается вариант с ( , и результат остаётся отсортированным. Объём работы не меняется; учёт переносится со стека вызовов на собственный стек.

СреднеПоиск с возвратом Рекурсия

+10

Строка из круглых скобок считается правильно сформированной, если при чтении слева направо количество ) никогда не становится больше количества (, а в конце оба количества равны. Поэтому (())() сформирована правильно, а ())( — нет: её третий символ закрывает пару, которая так и не была открыта.

Дано целое число n. Верните все правильно сформированные строки из n открывающих и n закрывающих круглых скобок, отсортированные в лексикографическом порядке, где ( идёт перед ).

Функция

generateParenthesis(n: integer) → string-array

ninteger: количество пар скобок
Возвращаетstring-array: каждую правильно сформированную строку из n пар в лексикографическом порядке

Ограничения

1 ≤ n ≤ 8
Для n = 8 ответ — 1 430 строк.

Примеры

Ввод: n = 3
Вывод: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Пояснение: Три пары можно расположить пятью правильными способами. ((())) открывает все три пары, прежде чем закрыть любую из них; поскольку ( сортируется первым, этот вариант стоит в начале списка; ()()() сразу закрывает каждую пару и стоит в конце.

Ввод: n = 1
Вывод: ["()"]
Пояснение: У одной пары есть единственный правильный вариант расстановки. Единственная другая строка из одной ( и одной ) — это )(, в которой закрывающая скобка стоит раньше, чем открывающая.

+10 скрытых тестов при отправке

Дополнительный вопрос

Можешь посчитать количество правильно сформированных строк для n пар, не генерируя их?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Правильно сформирована лишь небольшая доля строк длины 2n: 5 из 64 строк для n = 3 и 1 430 из 65 536 для n = 8. Идея, которая позволяет решить эту задачу, — строить строку слева направо, каждый раз добавляя только символ, который сохраняет её корректность, чтобы поиск никогда не заходил в ветвь, из которой нельзя получить завершённую строку. Допустимые действия определяют два счётчика: сколько символов ( вы уже поставили и сколько символов ). Если на каждом шаге пробовать ( перед ), строки сразу будут получаться отсортированными.

Составь каждую строку, затем проверь её

Идея

Прямой способ — заполнить 2n позиций всеми возможными способами и оставить строки с правильной структурой. В каждой позиции находится ( или ), поэтому всего получается 2^(2n) = 4^n строк. Рекурсивная функция ставит ( в следующую позицию, вызывает себя, затем ставит туда ) и снова вызывает себя, а каждую готовую строку проверяет.

При проверке строка проходится с отслеживанием баланса: плюс 1 для (, минус 1 для ). Строка имеет правильную структуру, если баланс никогда не опускается ниже 0 и в конце равен 0. Отрицательный баланс означает, что встретилась ), которой нечего закрывать, как третий символ в ())(.

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

Затраты составляют 4^n строк, каждая проверяется за O(n). При n = 8 это 65,536 строк для 1,430 ответов, то есть около 98% работы тратится впустую. Здесь алгоритм успевает завершиться, потому что n не больше 8, но с каждой дополнительной парой объём работы увеличивается в четыре раза; кроме того, он продолжает строить строки, начинающиеся с ), хотя уже первый символ позволяет их отбросить.

Алгоритм

Храните буфер из 2n символов и список ответов.
Напишите fill(pos). Если pos равно 2n, проверьте буфер и сохраните его, если он правильно сформирован.
В противном случае поместите ( в позицию pos и вызовите fill(pos + 1), затем поместите туда ) и вызовите функцию ещё раз.
Чтобы проверить строку, прибавляйте 1 за каждую ( и вычитайте 1 за каждую ). Отклоните её, как только баланс станет меньше 0 или если в конце он не равен 0.
Вызовите fill(0) и верните сохранённые строки, уже отсортированные.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Отслеживайте количество открывающих и закрывающих скобок

Идея

Перенесём проверку внутрь построения. Префикс всё ещё можно продолжить до правильной строки ровно тогда, когда соблюдаются два правила: в нём используется не более n открывающих скобок, и в нём никогда не бывает больше ), чем (. Поэтому на каждом шаге можно добавить (, пока opened < n, и ), пока closed < opened. Когда длина строки достигает 2n, оба счётчика равны n, и строка правильная — больше ничего проверять не нужно.

Вот всё дерево для n = 2. Из пустой строки разрешено добавить только (, поскольку пока не открыто ни одной скобки. После ( разрешены оба варианта. В ветке (( значение opened уже равно 2, поэтому подходит только ), дважды, и получается (()). В ветке () не открыто ни одной скобки, поэтому подходит только (, а затем ), и получается ()(). Каждая ветка заканчивается ответом: поиск никогда не строит строку, которую пришлось бы отбросить.

Ни один ответ не пропущен. Каждый префикс правильной строки соблюдает оба правила, поэтому поиск никогда не запрещает символ, который нужен этой строке следующим, а каждая строка создаётся один раз, поскольку её символы задают единственный путь по дереву. Порядок такой же, как в первом подходе: две строки впервые различаются в месте, где их пути расходятся, и в этой точке сначала рассматривается ветка (.

Каждый лист — это ответ, а число ответов для n пар равно числу Каталана C(n), которое растёт как 4^n / (n^1.5 √π). Каждый внутренний узел находится на пути хотя бы к одному листу, поэтому на каждый ответ приходится не более 2n внутренних узлов, а копирование ответа требует O(n). Общая сложность — O(n × C(n)) = O(4^n / √n): для n = 8 напрямую строятся 1,430 строк вместо проверки 65,536 строк.

Алгоритм

Сохраняй строящуюся строку и два счётчика — opened и closed, оба равными 0.
Если длина строки равна 2n, сохрани её копию и вернись.
Если opened < n, добавь (, вызови рекурсию с opened + 1 и удали его.
Если closed < opened, добавь ), вызови рекурсию с closed + 1 и удали его.
Начни с пустой строки и верни сохранённые строки, уже отсортированные, поскольку сначала проверяется (.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Ловушки и крайние случаи

Правила укладываются в два сравнения, поэтому ошибки скрываются в этих сравнениях и в порядке двух ветвей.

Если разрешать ) при условии closed < n вместо closed < opened, будут строиться строки вроде ())(, в которых закрывается пара, которую никогда не открывали.
Если проверять только, что строка содержит столько же (, сколько ), то будет принято )(. Баланс должен оставаться равным 0 или выше на каждом шаге, а не только в конце.
Если пробовать ) раньше (, правильные строки будут получены в обратном порядке, и сравнение с отсортированным ответом завершится неудачей.
Если сохранять общий буфер вместо его копии в языке, где списки или построители строк изменяемы: тогда каждый сохранённый ответ будет ссылаться на один и тот же буфер, который обратный поиск снова очищает.
Если выделить для массива результатов фиксированный размер 2n ответов или выбрать любое небольшое значение наугад: при n = 8 получится 1,430 ответов. Увеличивайте размер массива или сначала вычислите число Каталана.

Частые вопросы4

Какова временная сложность Generate Parentheses?

Решение с возвратом выводит числа Каталана C(n) = (2n)! / ((n+1)! n!) строк, количество которых растёт как 4^n / (n^1.5 √π). Длина каждой строки равна 2n, и поиск не тратит время на бесперспективные ветви, поэтому общее время составляет O(4^n / √n). Дополнительная память составляет O(n) для текущей строки и стека вызовов, не считая вывода.

Сколько существует корректных скобочных последовательностей для n пар?

Точно n-е число Каталана: 1, 2, 5, 14, 42, 132, 429 и 1,430 для n от 1 до 8. Это можно увидеть так: каждая правильно сформированная строка имеет вид ( + A + ) + B, где первая ( соответствует этой ), а A и B правильно сформированы и вместе содержат n-1 пар. Суммирование по размеру A даёт рекуррентное соотношение для чисел Каталана.

Почему условие closed < opened гарантирует корректную строку?

Строка становится некорректной, когда символ ) встречается без незакрытой ( перед ним, то есть когда количество ) превысило бы количество (. Если разрешать ) только при условии closed < opened, этого никогда не произойдёт, а если разрешать ( только при условии opened < n, оба счётчика достигнут n при длине 2n. Вместе эти два правила описывают каждый префикс правильно сформированной строки.

Можно ли решить задачу Generate Parentheses без рекурсии?

Да. Храни стек частичных состояний, каждое из которых представляет собой строку с двумя счётчиками, и расширяй состояние по тем же двум правилам. Если добавить в стек расширение ) перед расширением (, то первым извлекается вариант с (, и результат остаётся отсортированным. Объём работы не меняется; учёт переносится со стека вызовов на собственный стек.

Python

def generateParenthesis(n):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

n = 3

Ожидается

["((()))", "(()())", "(())()", "()(())", "()()()"]