2025-07-08

leetcode第22題”Generate Parenthese”描述如下:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

看到題第一想法依然是使用遞歸,思路基本是這樣的,在字符串長度增加的過程中,字符串中”{“的數量肯定要始終大於等於”}”的數量。

所以定義left和right兩個變量方便計數,初試為n,當left等於right時,顯然此時隻能添加”{“,當left小於right時,兩者都可以添加。結束條件為left和right都為0,同時由於left始終小於等於right,所以還要額外判斷僅當left為0的情況,這種情況顯然隻能加”}”。

/**
 * @param {number} n
 * @return {string[]}
 */
var add = function(left, right, stack, s) {
    if (left === 0 && right === 0) {
        stack.push(s);
        return;
    }
    if (left === right) {
        add(left - 1, right, stack, s + "(");
    } else if (left === 0) {
        add(left, right - 1, stack, s + ")");
    } else {
        add(left - 1, right, stack, s + "(");
        add(left, right - 1, stack, s + ")");
    }
};

var generateParenthesis = function(n) {
    var stack = [];
    add(n, n, stack, "");
    return stack;
};

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *