Generate Parentheses: бэктрекинг со счётчиками, числа Каталана и DP-решение

Коротко

Generate Parentheses — задача 22 на LeetCode, уровень Medium. Её любят давать как первую задачу на перебор: условие понятно за секунду, решение помещается в 15 строк, а по ходу видно, умеет ли кандидат отсекать ветви и оценивать экспоненциальную сложность. Если общий шаблон перебора с возвратом ещё не знаком, сначала загляните в статью про бэктрекинг, а здесь разберём одну задачу со всех сторон.

Условие

Дано целое $n$. Верните все правильные скобочные последовательности из $n$ открывающих и $n$ закрывающих круглых скобок. Порядок в ответе не важен.

Вход:  n = 3
Выход: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Вход:  n = 1
Выход: ["()"]

На LeetCode $1 \le n \le 8$. Маленькое ограничение — прямая подсказка: ответ экспоненциального размера, и задача не в том, чтобы найти полиномиальный алгоритм, а в том, чтобы не тратить время на заведомо плохие строки.

Что значит «правильная»

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

1. баланс ни разу не стал отрицательным;
2. в конце баланс равен нулю.

Проверка, когда видов скобок несколько, разобрана в статье про валидные скобки. Здесь вид один, и эти два условия — всё, что нужно для генерации.

Наивное решение: перебрать всё

Строка длины $2n$ из двух символов — это $2^{2n} = 4^n$ вариантов. Можно перебрать их все и оставить правильные:

from itertools import product


def generate_brute(n):
    result = []
    for chars in product('()', repeat=2 * n):
        balance = 0
        for ch in chars:
            balance += 1 if ch == '(' else -1
            if balance < 0:
                break
        if balance == 0:
            result.append(''.join(chars))
    return result

Работает, но тратит почти всё время впустую. Для $n = 8$ перебирается $65\,536$ строк, а правильных среди них $1430$ — около 2%. Чем больше $n$, тем меньше эта доля: правильных примерно $4^n / n^{3/2}$, то есть их доля убывает как $n^{-3/2}$. На моей машине для $n = 10$ перебор работал около трети секунды, а бэктрекинг ниже — около 10 миллисекунд.

На собеседовании это решение стоит назвать одной фразой и сразу перейти к нормальному: «можно перебрать $4^n$ строк и отфильтровать, но лучше не строить плохие строки вообще».

Бэктрекинг со счётчиками open и close

Будем строить строку по одному символу и сразу отсекать ветки, которые не могут привести к правильному ответу. Для этого держим два числа:

• open — сколько ( уже поставили;
• close — сколько ) уже поставили.

На каждом шаге два возможных хода:

• поставить (, если open < n — открывающих всего $n$;
• поставить ), если close < open — иначе баланс уйдёт в минус.

Когда длина строки дошла до $2n$, она гарантированно правильная: открывающих $n$, закрывающих $n$, а баланс ни разу не был отрицательным. Отдельной проверки в конце не нужно.

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

    def backtrack(open_count, close_count):
        if len(path) == 2 * n:
            result.append(''.join(path))
            return
        if open_count < n:
            path.append('(')
            backtrack(open_count + 1, close_count)
            path.pop()
        if close_count < open_count:
            path.append(')')
            backtrack(open_count, close_count + 1)
            path.pop()

    backtrack(0, 0)
    return result

Строку держим в списке path и склеиваем только в листе. Это классический приём бэктрекинга: сделать ход, спуститься, откатить ход. Можно передавать строку параметром — backtrack(s + '(', ...) — тогда откат не нужен, но каждый вызов создаёт новую строку. Для $n \le 8$ разницы не видно, на собеседовании подойдут оба варианта.

Приятное следствие порядка ходов: поскольку ( пробуем раньше ), а в ASCII ( меньше ), ответ выходит отсортированным лексикографически. Для $n = 3$ функция возвращает ровно ['((()))', '(()())', '(())()', '()(())', '()()()'].

Разбор на примере n = 2

Дерево вызовов (в скобках — open, close):

"" (0,0)
└── "(" (1,0)
    ├── "((" (2,0)
    │   └── "(()" (2,1)
    │       └── "(())" (2,2)  ✓
    └── "()" (1,1)
        └── "()(" (2,1)
            └── "()()" (2,2)  ✓

Из корня можно только (: закрывать нечего. Из (( — только ): открывающие кончились. Из () — только (: баланс нулевой. Ни одна ветка не заканчивается тупиком, каждый спуск доходит до ответа. Это и есть признак хорошего отсечения.

То же на JavaScript

function generateParenthesis(n) {
  const result = []
  const path = []
  const backtrack = (open, close) => {
    if (path.length === 2 * n) {
      result.push(path.join(''))
      return
    }
    if (open < n) {
      path.push('(')
      backtrack(open + 1, close)
      path.pop()
    }
    if (close < open) {
      path.push(')')
      backtrack(open, close + 1)
      path.pop()
    }
  }
  backtrack(0, 0)
  return result
}

Итеративный вариант со стеком

Рекурсия здесь неглубокая — не больше $2n + 1$ кадров, — так что переполнение стека не грозит. Но интервьюер может попросить решение без рекурсии. Заменяем стек вызовов явным стеком состояний (строка, open, close):

def generate_iterative(n):
    result = []
    stack = [('', 0, 0)]
    while stack:
        s, open_count, close_count = stack.pop()
        if len(s) == 2 * n:
            result.append(s)
            continue
        if close_count < open_count:
            stack.append((s + ')', open_count, close_count + 1))
        if open_count < n:
            stack.append((s + '(', open_count + 1, close_count))
    return result

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

Числа Каталана: почему ответов именно столько

Выпишем количество ответов для $n = 0, 1, 2, \ldots$: 1, 1, 2, 5, 14, 42, 132, 429, 1430. Это числа Каталана — одна из самых частых последовательностей в комбинаторике. Явная формула:

Для $n = 3$: $\binom{6}{3} = 20$, делим на 4 — получаем 5. Для $n = 8$: $\binom{16}{8} = 12\,870$, делим на 9 — $1430$.

Откуда рекуррента? Возьмём любую правильную последовательность и найдём ), которая закрывает самую первую (. Строка однозначно раскладывается в вид

где $A$ — правильная последовательность внутри первой пары, $B$ — правильная последовательность после неё. Если в $A$ ровно $i$ пар, то в $B$ остаётся $n - 1 - i$. Разложение единственное, потому что парная скобка для первой ( определена однозначно. Отсюда

Числа Каталана растут как

то есть почти как $4^n$, но с полиномиальной поправкой. Те же числа считают бинарные деревья из $n$ узлов, способы расставить скобки в произведении $n+1$ множителей, триангуляции выпуклого $(n+2)$-угольника и монотонные пути по сетке, не пересекающие диагональ. Больше про такие формулы — в статье про комбинаторику для программистов.

На собеседовании выводить формулу Каталана никто не попросит. Но фраза «ответов $C_n$, это числа Каталана, растут примерно как $4^n / n^{3/2}$» сильно облегчает разговор о сложности.

DP-решение через разложение (A)B

Рекуррента сразу даёт второй алгоритм. Все строки для $n$ пар — это все '(' + a + ')' + b, где a пробегает ответы для $i$ пар, b — для $n - 1 - i$, а $i$ — от $0$ до $n - 1$. Ответы для меньших $n$ считаем снизу вверх:

def generate_dp(n):
    dp = [['']]
    for k in range(1, n + 1):
        current = []
        for inside in range(k):
            for a in dp[inside]:
                for b in dp[k - 1 - inside]:
                    current.append('(' + a + ')' + b)
        dp.append(current)
    return dp[n]

База — dp[0] = ['']: ноль пар дают одну пустую строку, а не пустой список. Если ошибиться здесь, все остальные уровни тоже окажутся пустыми.

То же самое можно написать сверху вниз с @lru_cache — это мемоизация в чистом виде. Повторов в ответе не бывает: разложение (A)B единственно, поэтому каждая строка получается ровно одним способом.

Что выбрать? Бэктрекинг проще объяснить и он экономнее по памяти: держит одну текущую ветку, а не все ответы для всех $k \le n$. DP показывает, что вы видите структуру задачи, и пригодится, если интервьюер спросит про число ответов или про похожие задачи вроде Unique Binary Search Trees II (LeetCode 95). Порядок строк у DP другой, но в задаче он не важен.

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

Тут легко сказать неточно, поэтому разберём аккуратно.

Размер ответа. Строк $C_n$, каждая длины $2n$. Только на то, чтобы выписать ответ, нужно $\Theta(n \cdot C_n)$ времени и памяти. Подставляя асимптотику Каталана:

Время бэктрекинга. Каждый узел дерева вызовов — правильный префикс, то есть такой, который можно достроить до ответа. Значит, каждый узел лежит на пути от корня к какому-то листу-ответу. Путей $C_n$, длина каждого $2n + 1$, поэтому узлов не больше $(2n + 1) \cdot C_n$. Проверено: при $n = 8$ функция делает 6917 вызовов при 1430 ответах. Работа в узле — $O(1)$, плюс $O(n)$ на join в каждом листе. Итого $O(n \cdot C_n)$ — асимптотически оптимально, лучше не бывает.

Память. Без учёта ответа — $O(n)$: глубина рекурсии и длина path. С ответом — $O(n \cdot C_n)$.

Частая неточность — назвать сложность бэктрекинга $O(2^{2n})$. Это верхняя граница, но грубая: она описывает полный перебор, а отсечение как раз и убирает почти все ветки. Если интервьюер спрашивает точнее, ответ — $O(4^n / \sqrt{n})$.

Типичные ошибки

Условие close < n вместо close < open. С таким условием можно поставить ) в самом начале и получить )(. Закрывающих не может быть больше, чем открывающих, — именно это ограничение и делает перебор правильным.

Проверка валидности в листе. Если ограничения на ходы выбраны верно, строка длины $2n$ уже правильная. Дополнительная проверка не ломает ответ, но добавляет $O(n)$ на лист и показывает, что вы не до конца доверяете своему инварианту.

Забытый откат. С общим списком path после рекурсивного вызова нужен path.pop(). Без него строки удлиняются и мусор переходит в соседние ветки.

Конкатенация в Java через String. s + "(" в цикле создаёт новые объекты. В Java используйте StringBuilder и setLength(len - 1) для отката.

dp[0] = [] вместо ['']. В DP-версии это обнуляет всё: произведение с пустым множеством пусто.

Использование set от дубликатов. Ни бэктрекинг, ни DP повторов не дают. Если они появились, ошибка в логике, и set её только прячет.

Где встречается и что спросят дальше

Задача хороша как разминка перед более тяжёлым перебором. После неё естественно идут:

• Subsets и перестановки — тот же шаблон «ход, спуск, откат», но без счётчиков;
• Combination Sum — перебор с ограничением на сумму вместо баланса;
• N ферзей — бэктрекинг, где отсечение сложнее, чем два сравнения;
• Remove Invalid Parentheses (LeetCode 301) — обратная задача: из строки с лишними скобками убрать минимум символов.

Типичные уточнения от интервьюера:

1. «Сколько будет ответов для n = 10?» — $C_{10} = 16\,796$.
2. «А если нужно не перечислить, а посчитать?» — DP по рекурренте Каталана за $O(n^2)$ или формула через биномиальный коэффициент.
3. «А если скобки трёх видов?» — счётчиков уже мало: нужно помнить порядок открытых скобок, то есть стек. Каждую закрывающую можно поставить, только если она совпадает с вершиной.
4. «Как вернуть k-ю строку в лексикографическом порядке без генерации всех?» — считать, сколько правильных достроек у префикса с ( в начале, и спускаться по дереву, как в задачах на k-ю перестановку.

Если на последнем вопросе вы уверенно говорите про число достроек префикса, интервьюер видит, что вы понимаете не шаблон, а структуру перебора. Это и есть то, ради чего задачу дают.