LeetCode Generate Parentheses（生成括號）

一、題目描述

給定 n，生成所有由 n 對括號組成的合法組合。

範例： n=3 → ["((()))","(()())","(())()","()(())","()()()"]

二、解題思路：DFS 回溯 + 剪枝

遞歸構建字符串，參數：剩餘左括號 left、剩餘右括號 right、當前串 str。
規則：
- 任意時刻左括號數 ≥ 右括號數（否則非法）
- 可加左括號：若 left > 0
- 可加右括號：若 left（即已用左括號多於右括號）
- 終止：left==0 && right==0，加入結果

三、代碼實現（Python）

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.dfs(n, n, "", result)
        return result

    def dfs(self, left, right, s, result):
        if left == 0 and right == 0:
            result.append(s)
            return
        if left > 0:
            self.dfs(left-1, right, s + "(", result)
        if right > left:
            self.dfs(left, right-1, s + ")", result)

# 測試
if __name__ == "__main__":
    assert Solution().generateParenthesis(3) == ['((()))','(()())','(())()','()(())','()()()']

四、複雜度分析

• 時間：O(4^n / √n) (卡特蘭數)
• 空間：O(n) 遞歸棧 + 結果存儲

本題為經典回溯生成問題，剪枝條件保證合法性。