021 Generate Parentheses.py

"""
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:

"((()))", "(()())", "(())()", "()(())", "()()()"
"""
__author__ = 'Danyang'
class Solution:
    def generateParenthesis(self, n):
        """
        :param n: integer
        :return: list of string
        """
        result = []
        self.generateParenthesisDfs(result, "", n, n)
        return result

    def generateParenthesisDfs(self, result, cur, left, right):
        """
        DFS
        Catalan Number
        :param result: result list
        :param cur: currently processing string
        :param left: number of left parenthesis remaining
        :param right: number of right parenthesis remaining
        """
        # trivial
        if left==0 and right==0:
            result.append(cur)
            return
        # add left parenthesis
        if left>0:
            self.generateParenthesisDfs(result, cur+"(", left-1, right)
        # add right parenthesis
        if right>left:
            self.generateParenthesisDfs(result, cur+")", left, right-1)

if __name__=="__main__":
    assert Solution().generateParenthesis(3)==['((()))', '(()())', '(())()', '()(())', '()()()']