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

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

Пример:

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

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

1⃣Использовать рекурсию для генерации всех возможных комбинаций.

2⃣Если еще можно открыть скобку — добавляем ( и уменьшаем счетчик открытых.

3⃣Если есть закрытые скобки, которые можно закрыть — добавляем ).

😎 Решение:

class Solution { 

    private array $answer = []; 
    private string $current = ''; 

    function generateParenthesis($n) { 
        $this->generateParentheses($n, 0); 
        return $this->answer; 
    } 

    function generateParentheses($toOpen, $toClose) { 
        if ($toOpen == 0 && $toClose == 0) { 
            $this->answer[] = $this->current; 
            return; 
        } 

        if ($toOpen > 0) { 
            $this->current .= '('; 
            $this->generateParentheses($toOpen - 1, $toClose + 1); 
            $this->current = substr($this->current, 0, -1); 
        } 

        if ($toClose > 0) { 
            $this->current .= ')'; 
            $this->generateParentheses($toOpen, $toClose - 1); 
            $this->current = substr($this->current, 0, -1); 
        }         
    } 
}

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