Генерация всех правильных скобочных последовательностей

Решение

Описание проблемы

Генерация всех правильных скобочных последовательностей (valid parentheses combinations) — это фундаментальная задача на использование рекурсии и backtracking. Правильная последовательность должна удовлетворять условиям:

• Количество открывающих скобок = количеству закрывающих
• На любой префиксной позиции количество открывающих скобок >= закрывающих

Подход решения

Используем рекурсивный backtracking алгоритм:

1. Отслеживаем количество оставшихся открывающих и закрывающих скобок
2. На каждом уровне проверяем условия:
   • Если открывающих > 0, можем добавить открывающую скобку
   • Если закрывающих > открывающих в текущей последовательности, можем добавить закрывающую
3. Когда обе переменные = 0, добавляем результат в ответ

Реализация на Python

def generateParentheses(n: int) -> list[str]:
    """Генерирует все правильные скобочные последовательности."""
    result = []
    
    def backtrack(current: str, open_count: int, close_count: int):
        # Базовый случай: все скобки использованы
        if open_count == 0 and close_count == 0:
            result.append(current)
            return
        
        # Добавляем открывающую скобку, если остались
        if open_count > 0:
            backtrack(current + "(", open_count - 1, close_count)
        
        # Добавляем закрывающую скобку, если больше открывающих
        if close_count > open_count:
            backtrack(current + ")", open_count, close_count - 1)
    
    backtrack("", n, n)
    return result

# Пример использования
print(generateParentheses(3))
# Выход: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Реализация на JavaScript/TypeScript

function generateParentheses(n: number): string[] {
    const result: string[] = [];
    
    function backtrack(
        current: string,
        openCount: number,
        closeCount: number
    ): void {
        if (openCount === 0 && closeCount === 0) {
            result.push(current);
            return;
        }
        
        if (openCount > 0) {
            backtrack(current + "(", openCount - 1, closeCount);
        }
        
        if (closeCount > openCount) {
            backtrack(current + ")", openCount, closeCount - 1);
        }
    }
    
    backtrack("", n, n);
    return result;
}

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

Временная сложность: O(4^n / √n)

• Это количество Каталановых чисел (n-е число Каталана)
• Для n=3: 5 последовательностей, для n=4: 14

Пространственная сложность: O(n)

• Глубина рекурсии = 2n (максимальная глубина стека вызовов)
• Не считая выходного массива

Ключевые особенности алгоритма

• Ранняя отсечка: Проверяем условия перед рекурсивным вызовом
• Валидация: Гарантируем, что закрывающих скобок можно использовать только если они не превысят открывающих
• Без дополнительной валидации: Генерируем только корректные последовательности, не нужна финальная проверка

Тестирование

assert generateParentheses(1) == ["()"]
assert generateParentheses(2) == ["(())", "()()"]
assert generateParentheses(3) == ["((()))", "(()())", "(())()", "()(())", "()()()"]
assert len(generateParentheses(4)) == 14