22. Generate Parentheses

Задача

Дано число n пар скобок. Сгенерируйте все возможные корректные комбинации скобок.

Примеры

Пример 1

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

Пример 2

Input: n = 1
Output: ["()"]

Решение

Решение

// Time:  O(4^n / √n) — это число Каталана
// Space: O(n) — глубина стека (длина строки 2n)
 
function generateParenthesis(n) {
    const result = [];
 
    function backtrack(currentString, open, close) {
        // Базовый случай: длина строки достигла 2*n
        if (currentString.length === n * 2) {
            result.push(currentString);
            return;
        }
 
        // Решение 1: Добавить открывающую
        if (open < n) {
            backtrack(currentString + "(", open + 1, close);
        }
 
        // Решение 2: Добавить закрывающую
        if (close < open) {
            backtrack(currentString + ")", open, close + 1);
        }
    }
 
    backtrack("", 0, 0);
    return result;
}