LeetCode 22 Generate Parentheses - 生成所有合法括號組合

題目翻譯

給定 n 對括號，生成所有合法的括號組合。合法定義：任意前綴中左括號數 ≥ 右括號數，且總數相等。例 n=3：((())), (()()), (())(), ()(()), ()()()。

回溯法（DFS）核心邏輯

遞歸構建字符串，維護兩個計數器：

• left：已使用的左括號數
• right：已使用的右括號數

每一步有兩種選擇（若合法）：

1. 若 left < n，可加左括號 '('，遞歸 (left+1, right)。
2. 若 right < left，可加右括號 ')'，遞歸 (left, right+1)。

終止條件：right == n（等價於 left == n && right == n），將當前字符串加入結果。

代碼實現 (C++ / Java / Python)

class Solution {
public:
    vector generateParenthesis(int n) {
        vector res;
        backtrack(res, "", 0, 0, n);
        return res;
    }
    void backtrack(vector& res, string cur, int left, int right, int n) {
        if (right == n) { res.push_back(cur); return; }
        if (left < n) backtrack(res, cur + '(', left + 1, right, n);
        if (right < left) backtrack(res, cur + ')', left, right + 1, n);
    }
};

public class Solution {
    public List generateParenthesis(int n) {
        List res = new ArrayList<>();
        backtrack(res, "", 0, 0, n);
        return res;
    }
    void backtrack(List res, String cur, int left, int right, int n) {
        if (right == n) { res.add(cur); return; }
        if (left < n) backtrack(res, cur + '(', left + 1, right, n);
        if (right < left) backtrack(res, cur + ')', left, right + 1, n);
    }
}

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(cur, left, right):
            if right == n:
                res.append(cur)
                return
            if left < n: dfs(cur + '(', left + 1, right)
            if right < left: dfs(cur + ')', left, right + 1)
        dfs("", 0, 0)
        return res

遞歸樹圖解 (n=3)

                    ""
                   /   \
                 (      (invalid)
                / \    
              ((   ()
             / \   / \
           (((  (() (()  ())
          /   / \  |    / \
        ...  ... ...  ... ...

只有滿足 right ≤ left ≤ n 的路徑才會展開，葉子節點即為合法組合。

複雜度

• 時間：O(C_n · n) — 卡特蘭數 C_n = (2n)!/(n!(n+1)!) 個結果，每個長度 2n。
• 空間：O(n) 遞歸棧 + O(C_n · n) 結果存儲。

總結

本題是回溯法生成括號序列的經典入門。關鍵在於「左括號數不超過 n、右括號數不超過左括號數」兩個約束條件。面試時畫出遞歸樹、說明剪枝邏輯、寫出三語言代碼，可完整展示基本功。