# Leetcode 22. Generate Parentheses

## 題解

### DFS Back Tracking

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        output = []
        def dfs(left: int, right: int, ans: str):
            if left < right or left > n or right > n: # 邏輯是如果左右配對，一定是左邊一個右邊一個，所以可以判定，如果右邊大於左邊，就代表這個組合是不可能的，直接剪枝，如果左邊或右邊大於需要配對的總長度，也剪枝
                return
            if n == left and n == right: # 左右剛好都等於需要的長度，代表這是我們想要的解答，加進解答裡面
                output.append(ans)
            else: # 窮舉所有組合
                dfs(left+1,right,ans+"(")
                dfs(left,right+1,ans+")")
        dfs(0,0,"")
        return output