022. Parenthesis generation

Given that n represents the logarithm of generated parentheses, write a function that generates all possible and valid combinations of parentheses.

n = 3             res=["((()))"."() () ()"."() () ()"."() () ()"."() () ()"]
Copy the code
class Solution:  # DFS
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []

        def generate(S=' ', left=0, right=0):# left and right: Number of generated left and right parentheses
            if len(S) == 2 * n:  The # n pair of parentheses has 2n characters
                ans.append(S)  # S: built parenthesis string
                return
            if left < n:
                generate(S + '(', left + 1, right)
            if right < left:  A close parenthesis can only be generated if the close parenthesis is missing
                generate(S + ') ', left, right + 1)

        generate()
        return ans
Copy the code