Monday, June 9, 2014

LeetCode (Python): 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:
"((()))", "(()())", "(())()", "()(())", "()()()"

Solution:

class Solution:
    # @param an integer
    # @return a list of string
    def generateParenthesis(self, n):
        solution = []
        self.generateParenthesisRec(n,0,0,[],solution)
        return solution
    
    def generateParenthesisRec(self, n, openParentheses, closeParentheses,tempSolution,solution):
        if closeParentheses == n:
            solution.append(''.join(tempSolution))
            return
        if openParentheses<n:
            tempSolution.append('(')
            self.generateParenthesisRec(n,openParentheses+1,closeParentheses,tempSolution,solution)
            tempSolution.pop()
        if closeParentheses<openParentheses:
            tempSolution.append(')')
            self.generateParenthesisRec(n,openParentheses,closeParentheses+1,tempSolution,solution)
            tempSolution.pop()

No comments :

Post a Comment