---

1. 題目

數字 $n$ 代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且 有效的 括號組合。

示例 1：

輸入：$n=3$
輸出：$["((()))","(()())","(())()","()(())","()()()"]$

示例 2：

輸入：$n=1$
輸出：$["()"]$

---

提示：

• $1\le n\le 8$

2. 思路及代碼實現（Python）

2.1 暴力法

該思路先生成所有的 $2^{2n}$ 個 “（” 和 “）” 字符串構成的序列，然后檢查生成的序列是否有效，一共有 $n$ 對括號，共 $2n$ 個字符，每個位置存在兩種不同的選擇，因此總共有 $2^{2n}$ 種序列。

為了生成所有序列，可以使用遞歸。長度為 $n$ 的序列就是在長度為 $n?1$ 的序列后加一個 “(” 或 “)”。為了檢查序列是否有效，我們遍歷這個序列，并使用一個變量 $bal$ 表示左括號的數量減去右括號的數量。如果在遍歷過程中 $bal$ 的值小于零，或者結束時 $bal$ 的值不為零，那么該序列就是無效的，否則它是有效的。前者說明，遍歷一段字符串時出現 “)” 大于 “(” 的數量，顯然說明該子串不能成對；而后者說明整個字符串的左右括號數并不相等。

該算法的時間復雜度為：$O(2^{2n}n)$，對于 $2^{2n}$ 個序列中的每一個，對其進行有效性的驗證的復雜度為 $O(n)$。而空間復雜度除了存儲答案組之外，還需要存儲探索答案的棧深，復雜度為 $O(n)$。

class Solution:def generateParenthesis(self, n: int):def generate(A):if len(A) == 2*n:if valid(A):ans.append("".join(A))else:A.append('(')generate(A)A.pop()A.append(')')generate(A)A.pop()def valid(A):bal = 0for c in A:if c == '(': bal += 1else: bal -= 1if bal < 0: return Falsereturn bal == 0ans = []generate([])return ans

執行用時：71 ms
消耗內存：16.54 MB

2.2 回溯法

上述方法是遍歷生成所有的可能的序列，然后再進行判斷，這里我們發現有可以改進的地方，就是在生成序列時，提前跟蹤序列的左右括號的數據，來決定擴展序列時所選擇的括號。例如，已有子序列的左括號數量不大于 $n$，則可以放置左括號，如果右括號數量小于左括號數量，可以放置一個右括號。

該算法的復雜度分析依賴于該有效序列可以回溯出 的元素個數。這證明是第 $n$ 個卡特蘭數$\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ ，這是由 $\frac{4^n}{n\sqrt{n}}$ 漸近界定的。因此時間復雜度為 $O(\frac{4^n}{\sqrt{n}})$。空間復雜度為保存答案和保存棧深的消耗，為 $O(n)$。

class Solution:def generateParenthesis(self, n: int):ans = []def backtrack(S, left, right):if len(S) == 2 * n:ans.append(''.join(S))returnif left < n:S.append('(')backtrack(S, left+1, right)S.pop()if right < left:S.append(')')backtrack(S, left, right+1)S.pop()backtrack([], 0, 0)return ans

執行用時：42 ms
消耗內存：16.55 MB

---

題解來源：力扣官方題解