22. Generate Parentheses

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/generate-parentheses
• topics: Recursion, String Manipulation, Dynamic Programming

Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Ideas

• Recursion, ensure that valid by checking the number of opened and closed parentheses
• Dynamic Programming Bottom-Up
• Dynamic Programming Top-Down

Code

Recursion

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
 
        def generate(open_count,close_count,s,ans):
            if open_count == close_count == n:
                ans.append(s)
                return
 
            if open_count < n:
                generate(open_count+1,close_count,s+'(',ans)
            
            if open_count > close_count:
                generate(open_count,close_count+1,s+')',ans)
 
        generate(0,0,"",ans)
 
        return ans

Dynamic Programming Bottom-Up

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = [[] for i in range(n + 1)]
        dp[0].append('')
        for i in range(n + 1):
            for j in range(i):
                dp[i] += ['(' + x + ')' + y for 
                    x in dp[j] for y in dp[i - j - 1]]
        return dp[n]

Dynamic Programming Top-Down

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        @cache
        def generate(k):
            if k == 0:
                return [""]
            result = []
            for i in range(k):
                for x in generate(i):
                    for y in generate(k - i - 1):
                        result.append(f"({x}){y}")
            return result
 
        return generate(n)