[leetcode]22. Generate Parentheses

22. 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:

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

 

class Solution(object):
    def makeCombi(self, prefix, n , openp, closep, result):
        #print(prefix)
        if openp < closep :
            return 
        if openp+ closep == 2*n :
            result.append(prefix)
            
        if openp < n:
            self.makeCombi(prefix+"(", n, openp+1, closep, result)
        if closep < openp:
            self.makeCombi(prefix+")",n, openp, closep+1, result)
        return 
        
    def generateParenthesis(self, n):
        result = []
        self.makeCombi("", n , 0, 0, result)
        return result