Problem statement

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

Solution

For each valid parentheses there smallest k, for which the first k symbols compose well-formed parentheses: (left)right. Let us ans[i] be all valid parentheses of length i. Then we can generate them using recursion. For every k in range(n+1) and for every i in range(k) we choose left part and right part and append it to final answer. Because we memorize our intermediate results, we can also say that we use dp approach here.

Complexity

Time complexity is O(C_n * n) = O(4^n/n^0.5), where C_n is Catalan number. Space complexity is the same.

Code

class Solution:
    def generateParenthesis(self, n):
        ans = [[] for _ in range(n+1)]
        ans[0] = [""]
        for k in range(n + 1):
            for i in range(k):
                for left in ans[i]:
                    for right in ans[k-i-1]:
                        ans[k].append("(" + left + ")" + right)
        
        return ans[-1]