Сложность: medium
Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.
Пример:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
👨💻 Алгоритм:
1️⃣Используем рекурсию (DFS) для генерации всех возможных комбинаций.
2️⃣Добавляем открывающую скобку, если их количество меньше n.
3️⃣Добавляем закрывающую скобку, если их количество меньше, чем открывающих.
😎 Решение:
class Solution:
def generateParenthesis(self, n: int):
def dfs(left, right, s):
if len(s) == n * 2:
res.append(s)
return
if left < n:
dfs(left + 1, right, s + '(')
if right < left:
dfs(left, right + 1, s + ')')
res = []
dfs(0, 0, '')
return res
Ставь 👍 и забирай 📚 Базу знаний