Generate Parentheses

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

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

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

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

Q: Можно ли решить задачу «Генерация скобок» без рекурсии?

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

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

+10

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

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

Функция

generateParenthesis(n: integer) → string-array

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

Ограничения

1 ≤ n ≤ 8
Для n = 8 ответ содержит 1,430 строк.

Примеры

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

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

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

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

Подсказки

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

Открыто 0 из 3

Решение

Лишь немногие строки длины 2n являются правильно сформированными: 1 430 из 65 536 для n = 8. Стройте каждую строку слева направо и добавляйте символ, только если префикс ещё можно завершить. Для этого нужны два счётчика, а перебор ( перед ) приводит к тому, что строки получаются отсортированными.

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

Идея

Заполните 2n позиций всеми комбинациями ( и ) — получится 4^n строк — и оставьте правильно сформированные. Чтобы проверить строку, пройдите по ней, поддерживая баланс: прибавляйте 1 для (, вычитайте 1 для ). Строка правильно сформирована, если баланс никогда не опускается ниже 0 и в конце равен 0. Если на каждой позиции ставить ( перед ), строки будут перечислены в отсортированном порядке.

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

Алгоритм

Храни буфер из 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 по ветви (( можно только дважды закрыть скобки, получив (()), а по ветви () можно только открыть и закрыть скобки, получив ()(). Каждая строка — это один путь по дереву, поэтому она появляется один раз. Поскольку ветвь ( идёт первой, вывод отсортирован.

Каждый лист — это ответ, поэтому объём работы пропорционален размеру вывода: O(4^n / √n).

Алгоритм

Храни формируемую строку и два счётчика, 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 или быть больше 0 на каждом шаге.
Пробовать ) раньше, чем (. В результате правильные строки выводятся в обратном порядке.
Сохранять общий буфер вместо его копии, если используются изменяемые списки или сборщики строк. Тогда каждый сохранённый ответ указывает на один и тот же буфер, который при возврате снова очищается.
Задавать размер массива результатов фиксированной длины наугад. Для n = 8 есть 1,430 ответов.

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

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

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

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

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

Можно ли решить задачу «Генерация скобок» без рекурсии?

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

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

Тест #1

Тест #2

Аргумент

n = 3

Ожидаемый вывод

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