Generate Parentheses Solutions in Python

# Source : https://leetcode.com/problems/generate-parentheses/
# Author : penpenps
# Time   : 2019-05-28

from typing import List

# Recursive with "(" and ")" separately and guarantee open and close num is equal
# Time Complexity: O(2^n)
# Space Complexity: O(n)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def helper(current, openNum, closeNum, n, ans):
            if len(current) == 2*n:
                ans.append(current)
                return
            if openNum < n:
                helper(current+"(", openNum + 1, closeNum, n, ans)
            if closeNum < openNum:
                helper(current+")", openNum, closeNum + 1, n, ans)
                
        ans = []
        helper("", 0, 0, n, ans)
        return ans

if __name__ == '__main__':
	solution = Solution()
	n = 3
	print(solution.generateParenthesis(n))

# Source : https://leetcode.com/problems/generate-parentheses/
# Author : penpenps
# Time   : 2019-05-28

from typing import List

# Traversal all combinations with left part length as i and right part as n-1-i 
# Time Complexity: O(2^n)
# Space Complexity: O(n)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        for i in range(n):
            left = self.generateParenthesis(i)
            if not left:
                left = [""]
            right = self.generateParenthesis(n-1-i)
            if not right:
                right = [""]
            for l in left:
                for r in right:
                    ans.append("("+l+")"+r)
        return ans

if __name__ == '__main__':
	solution = Solution()
	n = 3
	print(solution.generateParenthesis(n))

# Source : https://leetcode.com/problems/generate-parentheses/
# Author : penpenps
# Time   : 2019-05-28

from typing import List

# Traversal all combinations with left part length as i and right part as n-1-i 
# Time Complexity: O(2^n)
# Space Complexity: O(n)

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

if __name__ == '__main__':
    solution = Solution()
    n = 3
    print(solution.generateParenthesis(n))