難度：Medium.

給出 n 代表生成括號的對數(shù)，請你寫出一個函數(shù)，使其能夠生成所有可能的并且有效的括號組合。

例如，給出 n = 3，生成結果為：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

解析：
這里的相關標簽是：字符串，回溯算法.

回溯算法，即深度優(yōu)先搜索(depth-first-search). 相比于廣度優(yōu)先搜索，深度優(yōu)先搜索的優(yōu)點是：代碼好寫，主要是遞歸的思想。

可以參見【算法圖解】Week 2 遞歸。簡單來說：

1. 遞歸就是指調(diào)用自己。
2. 調(diào)用自己很容易進入無限循環(huán)，所以需要一個計數(shù)器。
3. 計數(shù)器的作用是告訴遞歸函數(shù)：什么時候停止。
4. 因而，每個遞歸函數(shù)有2個條件：基線條件(base case), 遞歸(recursive case)。
5. 基線條件(base case)：是指函數(shù)不再調(diào)用自己的條件。
6. 遞歸(recursive case)：是指函數(shù)調(diào)用自己的條件。
7. 棧有2種操作：壓入（插入），彈出（讀取&刪除）。
8. 所有函數(shù)的調(diào)用都會進入棧。
9. 遞歸函數(shù)的執(zhí)行過程就是不停的將帶有不用參數(shù)的自己本身壓入棧，直到符合基線條件，再層層彈出。
10. ?？赡芎荛L，這將占用大量的內(nèi)存。（避免）

這里判斷遞歸是否結束（基線條件）有2個標準：

1. 剩余的左括號數(shù)量 小于 右括號 數(shù)量，說明生成的字符串不是有效的括號組合，去掉。
2. 剩余的左括號數(shù)量 and 右括號 數(shù)量 等于 0， 說明生成的字符串是有效的括號組合，添加到輸出list里。

否則，繼續(xù)迭代。

代碼：

def generateParenthesis(n):
    result = []
    cur_str = ""
    
    def dfs (cur_str, l, r):
        if l == 0 and r == 0:
            result.append(cur_str)
            return 
        if r < l:
            return
        
        if l > 0:
            dfs(cur_str + "(", l-1, r)
        
        if r > 0:
            dfs(cur_str + ")", l, r-1)
    
    dfs(cur_str, n, n)
    return result