---
title: "#22 Generate Parentheses"
tags: LeetCode, Top100
---
#22 Generate Parentheses
==

題目描述
--
Given ==n== pairs of parentheses, write a function to *generate all combinations of well-formed parentheses*.

Example 1:
--
>Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

解題思維
--
利用遞迴，且限制 ==")"== 必須在有 =="("== 的形況產生。

Recursive
--

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []

        def recursive(thisP, left, right):
            if left == 0 or right == 0:
                thisP += ")"*right
                return res.append(thisP)
            recursive(thisP+"(", left-1, right)
            if right > left:
                recursive(thisP+")", left, right-1)
        left, right = n, n
        recursive("", left, right)
        return res