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