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:

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

Leetcode 22

思路： 可以用backtracking做，也可以用dp来做。

BT：

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        left = right = n
        res = []
        self.bt('', left, right, res)
        return res

    def bt(self, cur, left, right, res):

        if left>right or left<0 or right<0:
            return

        if not left and not right:
            res.append(cur)

        self.bt(cur+'(', left-1, right, res)
        self.bt(cur+')', left, right-1, res)

DP:

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        dp = [[] for _ in range(n+1)]
        dp[0] = ['']

        for i in range(1, n+1):
            for j in range(i):
                dp[i] += ['(' + x + ')'+ y for x in dp[j] for y in dp[i-j-1]]
        return dp[-1]

so = Solution()
so.generateParenthesis(3)