Задача: 22. Generate Parentheses
Сложность: medium

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

Пример:

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]  

👨‍💻Алгоритм:

1⃣Используем рекурсию для построения строк, начиная с пустой строки.

2⃣Добавляем открывающую скобку, если их количество меньше n, и вызываем рекурсивную функцию.

3⃣Добавляем закрывающую скобку, если их количество меньше количества открытых, и вызываем рекурсию.

😎Решение:

import Foundation

func generateParenthesis(_ n: Int) -> [String] {
    var result = [String]()
    generate(current: "", open: 0, close: 0, max: n, result: &result)
    return result
}

private func generate(current: String, open: Int, close: Int, max: Int, result: inout [String]) {
    if current.count == max * 2 {
        result.append(current)
        return
    }
    
    if open < max {
        generate(current: current + "(", open: open + 1, close: close, max: max, result: &result)
    }
    
    if close < open {
        generate(current: current + ")", open: open, close: close + 1, max: max, result: &result)
    }
}

Ставь 👍 и забирай 📚 Базу знаний