A DFS Python approach - 51ms


  • 0
    L
    class Solution:
        # @param {integer} n
        # @return {string[]}
        def generateParenthesis(self, n):
            if n == 0:
                return []
            if n == 1:
                return ['()']
    
            result = []
            nl = nr = n
            s = '('
            nl -= 1
            result=self.getNext(s,nl,nr)
            return result
    
        def getNext(self, s, nl, nr):
            currentResult = []
            if 0 < nl < nr:
                currentResult += self.getNext(s+'(', nl-1, nr)
                currentResult += self.getNext(s+')', nl, nr-1)
            if nl == 0 and nr > 0:
                s += ')'*nr
                return [s]
            if nl == nr and nl != 0:
                currentResult += self.getNext(s+'(', nl-1, nr)
            return currentResult

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.