Почему это работает
- ")" добавляется, только пока close < open, поэтому в любой точке строки перед ней ")" не больше, чем "(": по пути строка не может испортиться.
- "(" добавляется, только пока open < n, поэтому больше n таких скобок в строке не бывает; когда в ней 2n скобок, open = close = n, и она правильная.
- Каждая правильная строка находится: на каждом месте в ней стоит "(" или ")", которую счётчики разрешают, а прогон пробует обе. В запрещённые ветки прогон не заходит, поэтому в конце ничего проверять не нужно.
Сложность
Время O(√n × 4ⁿ): всего счётчики пропускают O(4ⁿ / √n) начал строк (они растут как числа Каталана), и каждый вызов собирает свою строку за 2n шагов. Память O(n²) помимо ответа: стек вызовов глубиной 2n, и у каждого вызова своя строка до 2n скобок.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗