Модуль 21 ⏱ ~13 мин чтения 📐 1 Mermaid диаграмм

10. Generate Parentheses

«Синтаксис — это дисциплина равновесия: ничто не может быть закрыто, пока не было открыто, и ничто не может остаться открытым вовек».
— Никлаус Вирт

Задача Generate Parentheses (LeetCode 22) гармонично завершает кластер поиска с возвратом:
Условие: Задано целое число $n$ — количество пар круглых скобок. Требуется сгенерировать все синтаксически правильные скобочные последовательности длины $2n$.

Правильная скобочная последовательность (ПСП) удовлетворяет двум строгим грамматическим инвариантам:

  1. В любом префиксе строки количество закрывающих скобок ')' не превышает количества открывающих '('.
  2. В конце строки суммарное количество '(' строго равно количеству ')'.

В отличие от задачи о ферзях, где ограничения были глобальными, здесь условия локальны и элементарно контролируются двумя целочисленными счетчиками. Задача демонстрирует, как правильная модель пространства состояний превращает слепой перебор в обход дерева путей Дика (Dyck Paths) и чисел Каталана без единой лишней тупиковой ветви.

Архитектура: Дерево правильных префиксов для $n = 3$

Вместо наивной генерации всех $2^{2n}$ строк с последующей валидацией через стек, мы строим строку посимвольно, допуская к добавлению только те символы, которые гарантированно не нарушают инвариант:

  • Символ '(' разрешено добавить, если число уже поставленных открывающих скобок open < n.
  • Символ ')' разрешено добавить, если число закрывающих скобок строго меньше открывающих: close < open.
flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc

    Root["Корень: \#quot;\#quot; (open=0, close=0)"]:::entry --> O1["\#quot;(\#quot; (1, 0)"]:::process

    O1 --> O2["\#quot;((\#quot; (2, 0)"]:::process
    O1 --> C1["\#quot;()\#quot; (1, 1)"]:::process

    O2 --> O3["\#quot;(((\#quot; (3, 0)"]:::process
    O2 --> C2["\#quot;(()\#quot; (2, 1)"]:::process

    O3 --> L1["\#quot;((()))\#quot;"]:::success

    C2 --> O21["\#quot;(()(\#quot; (3, 1)"]:::process
    C2 --> C22["\#quot;(())\#quot; (2, 2)"]:::process
    O21 --> L2["\#quot;(()())\#quot;"]:::success
    C22 --> L3["\#quot;(())()\#quot;"]:::success

    C1 --> O12["\#quot;()(\#quot; (2, 1)"]:::process
    O12 --> O123["\#quot;()((\#quot; (3, 1)"]:::process
    O12 --> C123["\#quot;()()\#quot; (2, 2)"]:::process
    O123 --> L4["\#quot;()(())\#quot;"]:::success
    C123 --> L5["\#quot;()()()\#quot;"]:::success

Количество валидных комбинаций для $n$ пар строго задается $n$-м числом Каталана:
$$C_n = \frac{1}{n+1}\binom{2n}{n}$$
Для $n = 3$: $C_3 = \frac{1}{4}\binom{6}{3} = \frac{20}{4} = 5$ комбинаций.
Наш алгоритм обходит ровно эти 5 путей, не совершая ни единого ошибочного шага!

Идиоматичная реализация на Go

Go 
package main

// generateParenthesis возвращает все валидные скобочные комбинации из n пар.
// Временная сложность: O(4^n / sqrt(n)) — асимптотика чисел Каталана
// Пространственная сложность: O(n) глубина стека и буфера cur
func generateParenthesis(n int) []string {
    if n <= 0 {
        return []string{""}
    }

    var result []string
    // Предвыделяем емкость под точную длину скобочной строки 2*n
    cur := make([]byte, 0, 2*n)

    var backtrack func(open int, close int)
    backtrack = func(open int, close int) {
        // Базовый случай: набрано ровно 2*n символов
        if len(cur) == 2*n {
            // Преобразование []byte в string создает иммутабельную копию строки
            result = append(result, string(cur))
            return
        }

        // Ветвь 1: Можем открыть новую скобку
        if open < n {
            cur = append(cur, '(')
            backtrack(open+1, close)
            cur = cur[:len(cur)-1] // Откат
        }

        // Ветвь 2: Можем закрыть открытую скобку
        if close < open {
            cur = append(cur, ')')
            backtrack(open, close+1)
            cur = cur[:len(cur)-1] // Откат
        }
    }

    backtrack(0, 0)
    return result
}

Взгляд под капот: Mechanical Sympathy

1. Переиспользование []byte против конкатенации строк

В наивных реализациях часто пишут:

Go 
// Антипаттерн:
backtrack(s + "(", open+1, close)

Конкатенация строк s + "(" на каждом шаге рекурсии аллоцирует в куче новый заголовок строки и новый массив байт. Для $n = 8$ при глубине 16 это создаст десятки тысяч мелких объектов в куче и вызовет остановку рантайма сборщиком мусора (Stop-The-World GC).
Использование предвыделенного среза cur := make([]byte, 0, 2*n):

  • Выделяет память ровно один раз при старте.
  • Операции append и cur[:len(cur)-1] происходят в пределах одного кэш-блока L1d.
  • Аллокация происходит исключительно в момент result = append(result, string(cur)) при фиксации валидного ответа.

2. Спекулятивное исполнение процессора (Branch Prediction)

В цикле backtrack два условия if open < n и if close < open абсолютно независимы (не объединены через else). Это позволяет конвейеру процессора спекулятивно вычислять обе ветви, минимизируя задержки предсказателя переходов.

Подводные камни и вопросы с собеседований

Резюме Кластера 10 (Backtracking)

Мы полностью завершили фундаментальный модуль алгоритмов поиска с возвратом:

  1. Теория: Трехфазный инвариант Choose $\rightarrow$ Explore $\rightarrow$ Unchoose, работа со стеком горутины и безаллокационный откат через path[:len(path)-1].
  2. Комбинаторные каркасы: Подмножества ($C(n,k)$ со сдвигом start+1), перестановки ($N!$ с visited и битовыми масками), неограниченные сочетания (start без сдвига).
  3. Борьба с дубликатами: Сортировка и фильтрация ветвей на одном горизонтальном уровне дерева (i > start && nums[i] == nums[i-1]).
  4. Пространственный поиск: Обход 2D-матриц с маскированием клеток in-place (board[r][c] = '#').
  5. Глобальные ограничения: Быстрые проекции диагоналей в $N$-Queens и локальный баланс счетчиков в ПСП.

В следующем кластере мы применим навыки обхода дерева состояний к графовым структурам данных — переходим к Поиску в глубину (DFS): 1. Теория. DFS.