Почему это итеративное создание круглых скобок требует меньше операций, чем подход «разделяй и властвуй», несмотря на со ⇐ Python

[Anonymous]

Я решал LeetCode 22 — Генерация круглых скобок и придумал итеративный подход, который создает комбинации путем вставки () в каждую позицию (, а также добавления в начало/добавления. Несмотря на то, что мой подход генерирует повторяющиеся кандидаты (обрабатывается набором), он выполняет меньше итераций внутреннего цикла, чем решение «разделяй и властвуй» из редакционной статьи LeetCode.
Мой итеративное решение:
python

Код: Выделить всё

def generateParenthesis(self, n: int) -> List[str]:
combinations = {"()"}
for _ in range(n - 1):
new_combinations = set()
for pattern in combinations:
new_combinations.add("()" + pattern)
new_combinations.add(pattern + "()")
for idx, char in enumerate(pattern):
if char == "(":
new_combinations.add(pattern[:idx + 1] + "()" + pattern[idx + 1:])
combinations = new_combinations
return list(combinations)

Редакционная статья LeetCode (разделяй и властвуй):
python

Код: Выделить всё

def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return [""]
answer = []
for left_count in range(n):
for left_string in self.generateParenthesis(left_count):
for right_string in self.generateParenthesis(n - 1 - left_count):
answer.append("(" + left_string + ")" + right_string)
return answer

Измеренные итерации внутреннего цикла:



n
Мое
Редакционное




1
0
1


2
2
4


3
10
15


4
40
55


5
152
200



Оба выдают идентичный результат (проверено). Я реализовал самые внутренние циклы: в моем я считаю итерации над символами; в редакционной статье я подсчитываю самые внутренние вызовы добавления.
Мои вопросы:

• Чем объясняется разница в количестве итераций? Редакционная статья генерирует каждую уникальную комбинацию ровно один раз, а моя генерирует дубликаты, которые отбрасываются набором. Интуитивно я ожидаю, что мой будет выполнять больше работы.
• Существует ли выражение в закрытой форме для количества итераций, выполняемых каждым подходом, как функции от n? Выходной размер — каталонское число C(n), но я не уверен, как получить количество итераций.
• Сохраняется ли меньшее количество итераций в моем подходе асимптотически, или редакционная статья в конечном итоге выигрывает для большего n?

Подробнее здесь: https://stackoverflow.com/questions/798 ... han-the-di