Алгоритм, выводящий все корректные комбинации пар круглых скобок

Под корректными комбинациями пар будем понимать правильно открытые и закрытые скобки. На вход подаётся число пар скобок, на выходе должны быть все возможные их комбинации в виде набора строк.

Первая мысль — использовать рекурсивный подход, который строит решение для f(n), добавляя пары круглых скобок в f(n-1). Это, конечно, правильная мысль.

Рассмотрим решение для n = 3:

(()())    ((()))    ()(())    (())()    ()()()

Как получить это решение из решения для n = 2?

(())    ()()

Можно расставить пары скобок в каждую существующую пару скобок, а также одну пару в начале строки. Другие места, куда мы могли вставить скобки, например в конце строки, получатся сами собой.

Итак, у нас есть следующее:

Но постойте! Некоторые пары дублируются! Строка ()(()) упомянута дважды! Если мы будем использовать данный подход, то нам понадобится проверка дубликатов перед добавлением строки в список. Реализация такого метода выглядит так:

Алгоритм работает, но не очень эффективно. Мы тратим много времени на дублирующиеся строки.

Избежать проблемы дублирования можно путем построения строки с нуля. Этот подход подразумевает, что мы добавляем левые и правые скобки, пока наше выражение остается правильным.

При каждом рекурсивном вызове мы получаем индекс определенного символа в строке. Теперь нужно выбрать скобку (левую или правую). Когда использовать левую скобку, а когда — правую?

  1. Левая скобка: пока мы не израсходовали все левые скобки, мы можем вставить левую скобку.
  2. Правая скобка: мы можем добавить правую скобку, если добавление не приведет к синтаксической ошибке. Когда появляется синтаксическая ошибка? Тогда, когда правых скобок больше, чем левых.

Таким образом, нам нужно отслеживать количество открывающих и закрывающих скобок. Если в строку можно вставить левую скобку, добавляем ее и продолжаем рекурсию. Если левых скобок больше, чем правых, то вставляем правую скобку и продолжаем рекурсию.

Поскольку мы добавляем левые и правые скобки для каждого индекса в строке, индексы не повторяются, и каждая строка гарантированно будет уникальной.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».