LeetCode Generate Parentheses：括號生成問題遞歸回溯完整解析

問題描述

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

核心遞歸策略

維護兩個計數器：left（已用左括號數）、right（已用右括號數）。每步嘗試：

1. 若 left < n，可添加 '('，遞歸 (left+1, right)
2. 若 right < left，可添加 ')'，遞歸 (left, right+1)
3. 終止條件：left == n && right == n，收集結果

關鍵不變量：永不允許 right > left，這自然剪枝了所有非法分支。

Java 實現

public class Solution {
    public List generateParenthesis(int n) {
        List res = new ArrayList<>();
        if (n == 0) return res;
        backtrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }

    private void backtrack(List res, StringBuilder cur, int left, int right, int n) {
        if (left == n && right == n) {
            res.add(cur.toString());
            return;
        }
        if (left < n) {
            cur.append('(');
            backtrack(res, cur, left + 1, right, n);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (right < left) {
            cur.append(')');
            backtrack(res, cur, left, right + 1, n);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

複雜度分析

• 時間：O(Cₙ) — 第 n 個卡特蘭數 Cₙ = (2n)!/(n!(n+1)!)，每個合法組合生成一次
• 空間：O(n) 遞歸棧 + O(Cₙ × n) 結果存儲

擴展思考

• 第 k 個組合：利用卡特蘭數性質直接構造，O(n²)
• 非遞歸實現：模擬棧或使用 BFS 狀態機
• 括號匹配驗證：單次掃描 O(n)，棧或計數器

調試技巧

對於回溯算法，建議在 n=2 或 3 時加入打印，觀察遞歸樹的展開順序與回溯點，特別關注 right < left 條件如何精確阻擋非法路徑。