首页 > itarticle > leetcode 022

leetcode 022

admin 11月 13, 2020 0

Generate Parentheses
Method
Solution

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

    [
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

Method

Use DFS method.

Solution

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        self.dfs('',0,0,n,res)
        return res
        
    def dfs(self, s, left, right, n, res):
        if len(s) == 2 * n:
            res.append(s)
            return
        if left < n:
            self.dfs(s+'(',left+1,right,n, res)
        if right < left:
            self.dfs(s+')',left,right+1,n, res)