22. Generate Parentheses

──────────────────────────────────────────────────────────────────────

給 n，列出所有由 n 對括號組成的合法組合。

思路

這一題和 46. Permutations 很類似，題目要求的就是要窮舉。

最好寫回溯法的題目通常都會符合人類的直覺。括號的特性是左括號跟右括號一定成雙成對出現，所以這題就是不斷地先把左括號放完、再放右括號，之後退回一個左括號，再往下繼續拼湊。以 3 對括號為例，產生的順序如下：

1. ((()))
2. (()())
3. (())()
4. ()(())
5. ()()()

兩個條件就決定了一切

終止條件很直接：當左右括號都用滿 n 個時，就是產生出一組可行解了，記錄到答案裡。

至於這一步要放左括號還是右括號，只有兩條規則：

規則	意思
`left < n`	左括號還沒用完就可以放
`right < left`	右括號的數量不能超過左括號

第二條是整題的核心。它其實就是括號合法性的定義：從左到右讀，任何一個前綴裡「已關閉的」都不能多於「已開啟的」，否則就會出現 ) 找不到對應的 (。

跟 20. Valid Parentheses 對照著看就很清楚 —— 那題是拿這個規則去驗證一個字串，這題是拿同一個規則去生成。

這個題目比較需要想的是回溯解法通常會有一個遞迴，在這個題目，左括號跟右括號各要進行一次遞迴。

剪枝在這題不是優化，是解法本身

一般的回溯題常常是「先窮舉、再篩掉不合法的」。這題如果那樣做，就是列出所有 $2^{2 n}$ 種 ( ) 的排列再逐一驗證 —— 而合法的只佔極小一部分：

n = 4    合法解 14 個     所有排列 256 種     只有 5.5% 合法
n = 8    合法解 1430 個   所有排列 65536 種   只有 2.2% 合法

比例還會隨 n 越變越糟。而 left < n 和 right < left 這兩個條件讓遞迴從頭到尾只走進合法的分支 —— 走到底的每一條路都是答案，一個都不用丟掉。

這就是 Backtracking 模板說的「剪枝是唯一能救時間複雜度的手段」最乾淨的例子：它把「生成後過濾」變成「只生成合法的」。

解題方向

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(curr = [], left = 0, right = 0):
            if left == n and right == n:
                ans.append(''.join(curr))
                return
            if left < n: # left can not exceeds n
                curr.append('(')
                backtrack(curr, left + 1, right)
                curr.pop()
            if right < left: # right can not exceeds left
                curr.append(')')
                backtrack(curr, left, right + 1)
                curr.pop()

        backtrack()
        return ans

curr.append(...) 和 curr.pop() 就是回溯的「做選擇 / 撤銷選擇」。curr 是路徑的性質，離開這條分支就得還原 —— 跟 46 的 used[i] = False、207 的 on_path.remove(...) 是同一件事。

ans.append(''.join(curr)) 一定要 join 成新字串（等於複製一份）。直接 ans.append(curr) 會把同一個 list 的參考存進去，後面的 pop 會把已經存好的答案改掉。這是回溯題最常見的坑。

兩個 if 是平行的不是 elif —— 同一層要先試左括號、再試右括號，這兩條分支都要走。也因為左括號永遠先試，輸出天然就是字典序（( 排在 ) 前面）。

補充

終止條件可以更短：if len(curr) == 2 * n 跟 left == n and right == n 等價 —— 因為 right ≤ left ≤ n，總長度到 2n 時只可能是兩邊都滿。原本的寫法比較直白，兩種都行。

合法括號組合的數量是卡特蘭數：

$C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})$

n:   1   2   3   4    5    6     7     8
個數: 1   2   5   14   42   132   429   1430

這個數列在很多「配對 / 巢狀」的計數問題裡都會出現（二元樹的形狀數、出入棧的序列數）。知道它的存在，主要的用處是估複雜度時知道答案本身就有指數多個。

相關題：20. Valid Parentheses（驗證一個字串合不合法）、32. Longest Valid Parentheses（找最長的合法子字串）、301. Remove Invalid Parentheses（刪最少的括號讓字串合法）。共同的骨架都是那個「前綴裡右括號不能多於左括號」的計數規則。

模板與其他回溯題見 Backtracking 模板。

複雜度

先講結論：這題不可能比 $O (4^{n} / \sqrt{n})$ 快，因為答案本身就有那麼多個。

時間 $O (\frac{4^{n}}{\sqrt{n}})$ — 卡特蘭數 $C_{n}$ 約是 $\frac{4^{n}}{n^{1.5} \sqrt{π}}$ ，每個答案還要花 $O (n)$ 去 join，相乘之後是 $O (n \cdot C_{n})$
空間 $O (n)$ — 遞迴深度是 $2 n$ ，curr 最長也是 $2 n$ ；輸出的 ans 不計

（原本這裡寫成 $O (n)$ 是錯的 —— 那是「印出一個答案」的成本，不是「產生全部答案」的成本。只要題目要求「列出所有解」，時間下界就是解的個數，回溯法幾乎都是這種形狀。）

這題的剪枝救不了量級，但救了常數：不剪枝是 $2^{2 n} = 4^{n}$ ，剪枝後是 $4^{n} / \sqrt{n}$ —— 差的是一個多項式因子。真正的意義在於「每一條走到底的路都是答案」，中間沒有任何白工。