(Medium #22) Generate Parentheses

Problem

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:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

My solution

class Solution:    
    def generateParenthesis(self, n):
        if n==1:
            return ["()"]
        else:
            prelist = self.generateParenthesis(n-1)
            out = []
            for i in range(len(prelist)):
                out.append("(" + prelist[i] + ")")
                
            for k in range(1,int(n/2)+1):
                list1 = self.generateParenthesis(k)
                list2 = self.generateParenthesis(n-k)
                
                for p in range(len(list1)):
                    cand1 = list1[p]
                    for q in range(len(list2)):
                        cand2 = list2[q]
                        
                        out.append(cand1 + cand2)
                        out.append(cand2 + cand1)
            return list(set(out))          
Runtime: 40ms, Memory: 14.1MB

Other people solution

class Solution:
    # @param an integer
    # @return a list of string
    def generateParenthesis(self, n):
        result = []
        def generate(result, prev, remained_front, allowed_back):
            if remained_front == 0:
                for i in range(allowed_back):
                    prev += ")"
                result.append(prev)
                return
            if remained_front > 0:
                generate(result, prev+"(", remained_front-1, allowed_back+1)
            if allowed_back > 0:
                generate(result, prev+")", remained_front, allowed_back-1)
            
        generate(result,"(", n-1, 1)
        return result 
Runtime: 36ms, Memory: 14MB

댓글