Условие задачи

Дано n пар скобок. Напишите функцию, которая генерирует все возможные комбинации правильных скобочных последовательностей.

Объяснение

Необходимо написать функцию generate_parentheses(n: int) -> List[str], которая будет принимать на вход целое число n - количество пар скобок, и возвращать список строк - все возможные правильные скобочные последовательности.

Подробное объяснение

Правильная скобочная последовательность - это последовательность скобок, которая удовлетворяет следующим условиям:

1. Количество открывающих и закрывающих скобок совпадает.
2. Скобки расположены таким образом, что каждая открывающая скобка имеет соответствующую закрывающую скобку, и наоборот.

Например, для n=3 возможны следующие правильные скобочные последовательности:

• "((()))"
• "(()())"
• "(())()"
• "()(())"
• "()()()"

Решение по шагам

1. Создаем пустой список result для хранения всех возможных комбинаций скобок.
2. Начинаем рекурсивный процесс с помощью функции generate(curr, left, right), которая принимает три аргумента: curr - текущая скобочная последовательность, left - количество оставшихся открывающих скобок, right - количество оставшихся закрывающих скобок.
3. Если left и right равны 0, то добавляем текущую скобочную последовательность curr в список result.
4. Если left больше 0, то рекурсивно вызываем функцию generate с добавлением открывающей скобки ( в текущую последовательность curr и уменьшением значения left на 1.
5. Если right больше 0 и right больше left, то рекурсивно вызываем функцию generate с добавлением закрывающей скобки ) в текущую последовательность curr и уменьшением значения right на 1.