22. Generate Parentheses

Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, givenn= 3, a solution set is:

[

  "((()))",

  "(()())",

  "(())()",

  "()(())",

  "()()()"

]

这道题目非常符合动态规划的的方法，所以我们这里采用该方法进行解题，先把左边括号加到底，然后右括号加到底。然后逐渐往回退只要是符合左右括号都为零就符合要求

class Solution:

    def generateParenthesis(self, n):

        """

        :type n: int

        :rtype: List[str]

        """

        res_ = []

        self.dfs(n,n,'',res)

        return res

    def dfs(self,left,right,s,res):

        if left == 0 and right == 0:

            res.append(s)

        else:

            if left > 0:

                self.dfs(left-1,right,s+'(',res)

            if right > left:

                self.dfs(left,right-1,s+')',res)