LeetCode 22：括號生成 - 遞歸回溯法詳解

問題描述

給定 n 對括號，生成所有合法的括號組合。例如 n=3 時輸出：((())), (()()), (())(), ()(()), ()()()。

核心思路：雙計數器約束

利用兩個計數器追蹤剩餘可用括號：

• left：剩餘可放入的 ( 數量
• right：剩餘可放入的 ) 數量

關鍵約束：任意時刻 right > left 才能放入 )。因為已放入的 ( 數量 = n - left，已放入的 ) 數量 = n - right。合法性要求：已放入的 ( ≥ 已放入的 )，即 n-left ≥ n-right ⇒ right ≥ left。嚴格大於是因為相等時放 ) 會導致前綴右括號多於左括號。

遞歸策略

1. 基礎情況：left == 0，直接補齊 right 個 )，加入結果集
2. 嘗試放 (：若 left > 0，放入後遞歸 (left-1, right)
3. 嘗試放 )：若 right > left，放入後遞歸 (left, right-1)

完整代碼

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        if (n <= 0) return res;
        string cur = "(";
        dfs(res, cur, n-1, n);  // 第一個必須是 (
        return res;
    }
    
    void dfs(vector<string>& res, string& cur, int left, int right) {
        if (left == 0) {
            cur.append(right, ')');
            res.push_back(cur);
            cur.resize(cur.size() - right);  // 回溯恢復
            return;
        }
        // 放 (
        cur.push_back('(');
        dfs(res, cur, left-1, right);
        cur.pop_back();
        
        // 放 )
        if (right > left) {
            cur.push_back(')');
            dfs(res, cur, left, right-1);
            cur.pop_back();
        }
    }
};

關鍵點解析

• 字符串引用傳遞 + 回溯：避免大量字符串拷貝，push_back/pop_back 實現原地修改
• 基礎情況優化：left==0 時直接 append 所有右括號，避免逐個遞歸
• 初始條件：第一個字符必須是 (，故初始 left=n-1, right=n

複雜度分析

• 時間：O(C_n * n)，C_n = (2n)!/(n!(n+1)!) 為第 n 個卡特蘭數，每個合法組合構建需 O(n)
• 空間：O(n) 遞歸棧 + O(C_n * n) 結果存儲

擴展：迭代法與位運算

也可用位掩碼枚舉 2n 位中選 n 位為 (，再驗證合法性，但效率遠低於回溯剪枝。

測試用例

n=1: ()
n=2: (()), ()()
n=3: ((())), (()()), (())(), ()(()), ()()()