Leetcode 22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

We can use DFS to solve the problem. The first solution is very straight forward, while the second solution uses math analysis: valid parentheses always have no less '(' than ')' in the generate process.

The number of result is actually Catalan number.

Solution 1:

# T:O(4^n / n^(3/2)) S:O(n)
class Solution:
    # @param {integer} n
    # @return {string[]}
    def generateParenthesis(self, n):
        dp = {0:[''], 1:['()']}
        def dfs(k):
            if not k in dp:
                dp[k] = []
                for i in range(k):
                    for inner in dfs(i):
                        for outter in dfs(k - i - 1):
                            dp[k].append('('+inner+')'+outter)
            return dp[k]
        return dfs(n)

Run Time: 60 ms

Solution 2:

# T:O(4^n / n^(3/2)) S:O(n)
class Solution:
    # @param an integer
    # @return a list of string
    def generateParenthesis(self, n):
        result = []
        self.generateParenthesisRecu(result, "", n, n)
        return result
    
    def generateParenthesisRecu(self, result, current, left, right):
        if left == 0 and right == 0:
            result.append(current)
        if left > 0:
            self.generateParenthesisRecu(result, current + "(", left - 1, right)
        if left < right:
            self.generateParenthesisRecu(result, current + ")", left, right - 1)

Run Time: 48 ms