###### tags: `Leetcode` `medium` `backtracking` `python` `Top 100 Liked Questions`

# 22. Generate Parentheses

## [題目連結:] https://leetcode.com/problems/generate-parentheses/

## 題目:
Given ```n``` pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

**Example 1:**

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

**Example 2**:

Input: n = 1
Output: ["()"]

## 解題想法:
* 要求輸出n對括號的所有合法組合
* 當長度=2*n 表示可以加入res
* 先判斷左刮是否有剩
* 遞迴求(左數量+1,右數量)
* 再判斷右括是否數量<左刮數量(確保合法)
* 遞迴求(左數量,右數量+1)

## Python:

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.res = []
        cur = ""
        self.dfs(cur,n,0,0)
        return self.res
    def dfs(self,cur,n,left,right): #左括右括
        #若總數已滿即可加到ans
        if len(cur)==n*2:
            self.res.append(cur)
            return None
        #若還有多餘的(
        if left<n:
            self.dfs(cur+"(",n,left+1,right)
        #若目前的)量小於(
        if right<left:
            self.dfs(cur+")",n,left,right+1)
                
if __name__ == '__main__':
    result = Solution()
    ans = result.generateParenthesis(3)
    print(ans)