Генерация комбинаций скобок

Генерация комбинаций скобок

Это классическая задача на рекурсию и backtracking. Нам нужно генерировать все валидные скобочные последовательности (где каждая открывающая скобка имеет парную закрывающую).

Ключевая идея

Мы строим строку рекурсивно, на каждом шаге решая:

• Можем ли добавить открывающую скобку?
• Можем ли добавить закрывающую скобку?

Ограничения для валидности:

1. Количество открывающих скобок ≤ n
2. Количество закрывающих скобок ≤ количества открывающих (в любой момент)

Рекурсивное решение

def generate_parentheses(n):
    """
    Генерирует все валидные комбинации n пар скобок.
    
    Сложность: O(4^n / sqrt(n)) время, O(n) доп. память
    (количество валидных последовательностей = число Каталана)
    """
    result = []
    
    def backtrack(current, open_count, close_count):
        """
        current: текущая строка
        open_count: используя открывающих скобок
        close_count: использовано закрывающих скобок
        """
        # Базовый случай: построена полная последовательность
        if len(current) == 2 * n:
            result.append(current)
            return
        
        # Добавляем открывающую скобку, если не достигли лимита
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        
        # Добавляем закрывающую скобку, если есть закрытыми открывающимися
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)
    
    backtrack("", 0, 0)
    return result

Пошаговое выполнение для n=2

gen_parentheses(2)
backtrack("", 0, 0)
├─ open=1: backtrack("(", 1, 0)
│  ├─ open=2: backtrack("((", 2, 0)
│  │  ├─ close=1: backtrack("(()", 2, 1)
│  │  │  └─ close=2: backtrack("(())", 2, 2) → ДОБАВИТЬ "(())"
│  ├─ close=1: backtrack("()", 1, 1)
│  │  ├─ open=2: backtrack("()(", 2, 1)
│  │  │  └─ close=2: backtrack("()()", 2, 2) → ДОБАВИТЬ "()()"

Результат: ["(())", "()()"]

Лучше понять с визуальным деревом

n=2 (нужно 2 открывающих и 2 закрывающих)

                      ("", 0, 0)
                     /           \open=1
                   /               \
            ("(", 1, 0)
            /           \open=2
          /               \
      (("((", 2, 0)
      /           \close=1
    /               \
("(()", 2, 1)
|      \close=2
|        \
| "(())"  ← Решение

И так далее...

Альтернатива: Итеративное решение

def generate_parentheses_iterative(n):
    """
    Итеративное решение с явным стеком вместо рекурсии
    """
    result = []
    stack = [("(", 1, 0)]  # (текущая строка, открытых, закрытых)
    
    while stack:
        current, open_count, close_count = stack.pop()
        
        if len(current) == 2 * n:
            result.append(current)
            continue
        
        # Попытка добавить закрывающую скобку (сначала, для порядка)
        if close_count < open_count:
            stack.append((current + ")", open_count, close_count + 1))
        
        # Попытка добавить открывающую скобку
        if open_count < n:
            stack.append((current + "(", open_count + 1, close_count))
    
    return result

Полная реализация с примерами

def generate_parentheses(n):
    result = []
    
    def backtrack(current, open_count, close_count):
        # Выход из рекурсии
        if len(current) == 2 * n:
            result.append(current)
            return
        
        # Можем добавить открывающую скобку?
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        
        # Можем добавить закрывающую скобку?
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)
    
    backtrack("", 0, 0)
    return result

# Тесты
print(generate_parentheses(0))  # [""]
print(generate_parentheses(1))  # ["()"]
print(generate_parentheses(2))  # ["(())", "()()"]
print(generate_parentheses(3))
# ["((()))", "(()())", "(())()", "()(())", "()()()"]

print(f"\nn=3: {len(generate_parentheses(3))} комбинаций")
print(f"n=4: {len(generate_parentheses(4))} комбинаций")

Анализ сложности

Количество валидных последовательностей = число Каталана:

C_n = (2n)! / ((n+1)! * n!) = Θ(4^n / n^(3/2))

Временная сложность: O(4^n / sqrt(n)) — генерируем все Каталанские числа

Пространственная сложность: O(n) — глубина рекурсии + стек вызовов

Оптимизированная версия

def generate_parentheses_fast(n):
    if n == 0:
        return [""]
    
    # Кэширование для меньших значений
    cache = {}
    
    def helper(n):
        if n in cache:
            return cache[n]
        
        if n == 0:
            return [""]
        if n == 1:
            return ["()"]
        
        result = []
        for i in range(n):
            # Разбиваем на левую и правую части
            left = helper(i)        # i открывающих
            right = helper(n - 1 - i)  # n-1-i открывающих
            
            for l in left:
                for r in right:
                    result.append("(" + l + ")" + r)
        
        cache[n] = result
        return result
    
    return helper(n)

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

Проверка валидности скобок

def is_valid_parentheses(s):
    """
    Проверяет, валидна ли скобочная последовательность
    """
    balance = 0
    for char in s:
        if char == "(":
            balance += 1
        else:
            balance -= 1
        
        # В любой момент закрывающих не должно быть больше открывающих
        if balance < 0:
            return False
    
    return balance == 0  # В конце должно быть сбалансировано

# Проверим результаты
for seq in generate_parentheses(3):
    assert is_valid_parentheses(seq)

Эта задача демонстрирует мощь backtracking — техники, где мы строим решение шаг за шагом и откатываемся при нарушении ограничений.