Задача с собеседования в eBay

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

Пример 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Пример 2:
Input: n = 1
Output: ["()"]

Ограничения:
1 <= n <= 8

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Известно, что правильная скобочная последовательность должна состоять из одинакового количества открывающих и закрывающих скобок, то есть общая длина правильной комбинации - n * 2.
Для решения задачи используем алгоритм поиска с возвратом, где на каждом шаге, в зависимости от условий, добавляем либо открывающую, либо закрывающую скобку. После построения полной правильной комбинации и её сохранения мы не прерываем поиск, а последовательно возвращаемся по стеку вызовов до последней точки выбора и исследуем другие ветки из этой точки.

Создаём два списка:
result - для хранения найденных правильных комбинаций;
combination - временный список для "собирания" текущей комбинации.
Запускаем рекурсивную функцию backtrack(open_count, close_count) для генерации комбинаций, отслеживая кол-во открывающих и закрывающих скобок.
Базовый случай: если длина текущей комбинации достигла n * 2 - добавляем готовую комбинацию в result и возвращаемся.
Рекурсивное ветвление: можем добавить открывающую, если ещё не использованы все n открывающих скобок. Можем добавить закрывающую, если кол-во открывающих скобок больше кол-ва закрывающих, это условие гарантирует, что у нас есть незакрытая открывающая скобка, которую можно закрыть.
Для каждого допустимого выбора:
- добавляем скобку в combination
- вызываем рекурсию с обновленными параметрами
- удаляем последнюю добавленную скобку для возврата к развилке и исследованию других путей построения последовательности.
Функция завершается, когда полностью исследовано дерево возможных комбинаций. Для начального вызова backtrack(0, 0) это означает, что исследованы все пути первого if, а путь второго if невозможен, так как последовательность не может начаться с закрывающей скобки.

Сложность
Экспоненциальная: O(4ⁿ/√n) - по времени (определяется n-ым числом Каталана Cₙ, равным кол-ву правильных скобочных последовательностей для n пар скобок); в кач-ве упрощения иногда говорят о сложности O(2**n)
O(n) - по памяти

Код
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
combination = []

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

backtrack(0, 0)
return result

@algoses