22. Generate Parentheses

📘 題目敘述

給你 n 對括號，請寫一個函式，產生所有合法的括號組合。

條件限制

• 1 <= n <= 8

🧠 解題思路（一）用遞迴

這題的重點是：

我不是先把所有長度 2n 的括號字串都列出來再檢查，而是在遞迴的過程中，只往合法的方向繼續走。

因為一個合法括號字串要滿足兩件事：

• 左括號 ( 總數最後要剛好是 n
• 任何一個過程中，右括號 ) 的數量都不能超過左括號 ( 的數量

所以我在遞迴時只記兩個數：

• left：目前已經放了幾個 (
• right：目前已經放了幾個 )

然後用這兩個條件控制下一步：

• 如果 left < len，代表左括號還沒放滿，可以繼續放 (
• 如果 right < left，代表目前右括號數量還沒超過左括號，這時才可以放 )

這樣遞迴下去，到最後 left == len && right == len 時，代表這個字串長度已經滿了，而且整段過程都沒有違反合法條件，所以它一定是一個合法答案，可以直接放進 ans。

這份程式的核心想法就是：

用 DFS / backtracking 一個字一個字往後放，並且在過程中就把不合法的情況剪掉。

所有變數

• ans：存所有合法括號字串的答案陣列
• len：括號對數，也就是題目的 n
• left：目前字串中已經放了幾個左括號 (
• right：目前字串中已經放了幾個右括號 )
• s：目前遞迴到這一步所組出來的括號字串

🪜 主要流程步驟（一）

1. 先用 len 記住總共要放幾對括號

在 generateParenthesis 裡，先把輸入的 n 存到成員變數 len：

len = n;

這樣後面的遞迴函式 dop 就可以直接知道：

• 左括號最多放到 len
• 右括號最多也放到 len

2. 從空字串開始做遞迴

接著從：

dop(0, 0, "");

開始。

意思是：

• 現在一個左括號都還沒放，所以 left = 0
• 一個右括號也還沒放，所以 right = 0
• 目前字串是空字串 ""

然後讓 dop 一路往下去試所有合法的擴展方式。

3. 如果左括號還沒放滿，就可以先放一個左括號

在 dop 裡先判斷：

if (left < len) {
    dop(left + 1, right, s + '(');
}

這段的意思是：

• 只要目前左括號數量還沒到 n
• 我就可以再補一個 (

所以遞迴到下一層時：

• left + 1
• right 不變
• s 後面多接一個 '('

這一步是在建立所有「可能的左括號延伸」。

4. 如果右括號數量還小於左括號，才可以放右括號

接著判斷：

if (right < left) {
    dop(left, right + 1, s + ')');
}

這是這題最重要的合法性條件。

因為合法括號字串的任何前綴都不能出現：

• 右括號比左括號還多

所以只有在 right < left 的時候，才代表目前可以安全地放一個 )。

這樣遞迴到下一層時：

• left 不變
• right + 1
• s 後面多接一個 ')'

這一步其實就是在做剪枝：

• 不合法的情況根本不往下遞迴
• 所以最後留下來的都會是合法答案

5. 當左右括號都放滿時，就把這個字串加入答案

if (left == len && right == len) {
    ans.push_back(s);
}

當這個條件成立時，表示：

• 左括號已經放了 n 個
• 右括號也已經放了 n 個

也就是整個字串長度已經到 2n，而且前面又都遵守 right < left 的規則，所以這個 s 一定是合法括號字串。

這時就把它存進 ans。

6. 為什麼這樣能保證答案全部合法

這份程式沒有額外寫一個檢查函式去驗證字串是否合法，因為合法性是直接在遞迴過程中保證的。

原因是：

• 左括號最多只能放到 n 個
• 右括號最多只能放到 n 個
• 只有在 right < left 時才能放 )

所以不可能出現像這種不合法前綴：

• ")("
• "())("
• "))..."

也就是說，程式不是「先亂生再篩」，而是「只生合法路徑」。

7. 最後回傳 ans

當整棵遞迴樹都跑完之後，ans 裡面就會放好所有合法的括號組合。

所以最後直接：

return ans;

就可以了。

⏱️ 複雜度

• 時間複雜度：O(答案總數 × n) 每個合法字串長度都是 2n，而遞迴過程會把所有合法答案建出來。
• 空間複雜度：O(答案總數 × n) 需要儲存所有答案字串，遞迴本身也會有呼叫堆疊。

💻 程式碼實作（一）

class Solution {
public:
    vector<string> ans;
    int len;
    void dop(int left, int right, string s) {
        if (left < len) {
            dop(left + 1, right, s + '(');
        }
        if (right < left) {
            dop(left, right + 1, s + ')');
        }
        if (left == len && right == len) {
            ans.push_back(s);
        }
        return;
    }
    vector<string> generateParenthesis(int n) {
        len = n;
        dop(0, 0, "");
        return ans;
    }
};

🧠 解題思路（二）直接函數遞迴，但會重複 WA

我這份寫法是用函數遞迴去做：

先把 n - 1 對括號的所有合法答案算出來，然後對每個字串 s，再試著用三種方式把新的一對括號加進去：

• 把整個 s 包起來：'(' + s + ')'
• 把 () 放在左邊："()" + s
• 把 () 放在右邊：s + "()"

這樣的想法很直觀，因為看起來像是在把 n - 1 對括號擴充成 n 對括號。

不過這份程式也有一個重點要注意：

這三種擴充方式不是唯一的，所以同一個合法答案可能會被重複產生。

例如某些字串，可能既能從前一個答案做「右邊加 ()」得到，也能從另一個答案做「外面包一層」得到。 所以這種遞迴生成法的問題不是會產生非法字串，而是會產生重複答案。

也就是說，這份程式的核心想法是：

先遞迴取得 n - 1 的所有合法括號字串，再對每個字串用三種方式擴充成 n。 但因為不同來源可能生成同一個字串，所以結果裡會有重複。

所有變數

• n：目前要產生幾對括號
• v：遞迴取得的 n - 1 對括號的所有結果
• ans：目前這一層要回傳的答案陣列
• s：從 v 中取出的某一個合法括號字串

🪜 主要流程步驟（二）

1. 先處理最小情況 n = 1

if (n == 1) {
    return {"()"};
}

如果只有一對括號，那答案只有一種，就是 "()"。

這也是整個遞迴的 base case。

2. 先遞迴求出 n - 1 對括號的所有答案

vector<string> v;
v = generateParenthesis(n - 1);

這一步的意思是：

現在不直接處理 n，而是先把比較小的問題 n - 1 解出來。

所以 v 裡面會放所有 n - 1 對括號的合法字串。

3. 準備一個新的 ans 來存這一層產生的結果

vector<string> ans;

這個 ans 是這次 generateParenthesis(n) 要回傳的結果。

接下來會把從 v 擴充出來的所有字串都放進去。

4. 對每個 n - 1 的合法字串 s，試三種擴充方式

for (string s : v) {
    ans.push_back('(' + s + ')'); // 夾起來的
    ans.push_back("()" + s);      // 左邊的
    ans.push_back(s + "()");      // 右邊的
}

這一段是整份程式的核心。

假設目前 s 是一個 n - 1 對括號的合法字串，那我就把新的一對括號加進去，方法有三種：

• (' + s + ')'
  • 代表把原本整串包起來
• "()" + s
  • 代表把一對新的括號直接接到左邊
• s + "()"
  • 代表把一對新的括號直接接到右邊

這三種方式產生出來的字串都還是合法括號字串，所以都可以放進 ans。

5. 為什麼這樣會重複

這份程式的問題就出在這裡：

不同的 s，經過不同擴充方式後，可能會產生一樣的結果。

也就是說，這個遞迴關係不是一對一的。

例如當 n = 3 時，n - 1 = 2 的答案有：

• "(())"
• "()()"

然後去做三種擴充時，有些最終字串可能會從不同來源重複被放進 ans。

所以這個方法雖然能生出很多合法括號字串，但沒有保證每個答案只出現一次。

6. 最後回傳 ans

return ans;

這份程式最後直接把 ans 回傳。

但因為前面提到的原因，這個 ans 可能會有重複答案，所以這份程式的遞迴想法可以理解，但結果並不是完整正確的去重版本。

⏱️ 複雜度

設 T(n) 表示這份遞迴程式在 generateParenthesis(n) 最後回傳的字串數量（包含重複）。

• 時間複雜度：O(T(n) · n) 每個產生出來的字串長度大約是 2n，可視為 O(n)，而整體要處理 T(n) 個字串。
• 空間複雜度：O(T(n) · n) 需要儲存這一層產生的所有字串，而且每個字串長度是 O(n)。

💻 程式碼實作（二）

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 1) {
            return {"()"};
        }
        vector<string> v;
        v = generateParenthesis(n - 1);
        vector<string> ans;
        for (string s : v) {
            ans.push_back('(' + s + ')'); // 夾起來的
            ans.push_back("()" + s);      // 左邊的
            ans.push_back(s + "()");      // 右邊的
        }
        ans.pop_back();
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/generate-parentheses/