22. Generate Parentheses

Question

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

Example 1

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Solution 1: Recursive

class Solution:
    def dfs(self, ans, prevPair, lftCnt, rhtCnt, pairSize):
        if (lftCnt + rhtCnt) == pairSize:
            ans.append(prevPair)
            return ans
        
        if lftCnt < pairSize // 2:
            ans = self.dfs(ans, prevPair+'(', lftCnt+1, rhtCnt, pairSize)
        if rhtCnt < lftCnt:
            ans = self.dfs(ans, prevPair+')', lftCnt, rhtCnt+1, pairSize)
        return ans
    
    def generateParenthesis(self, n: int) -> List[str]:
        ans = self.dfs([], "", 0, 0, 2*n)
        return ans

Time Complexity: O(2^N)
Space Complexity: O(N)

Solution 2: Iterative + DP

Time Complexity: O()
Space Complexity: O()

Reference

https://leetcode.com/problems/generate-parentheses/discuss/10100/Easy-to-understand-Java-backtracking-solution
https://leetcode.com/problems/generate-parentheses/discuss/10127/An-iterative-method.

Follow-up: Check if a Parentheses String Can Be Valid

TODO

Time Complexity: O()
Space Complexity: O()