[Search]LC 22. Generate Parentheses

Goal

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

Example 1:

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

Example 2:

Input: n = 1
Output: ["()"]

Strategy

• DFS + Two Pointers (left, right counters)
• Simply use the pointers to keep track of the count
• When l>r → we skip and no action because the number of remaining ‘(‘ should always be less than ‘)’ !
• Else we append the left or right parentheses, and pop after each recursion call

Complexity

• Time: O(2^n) with n = the number of each parentheses
• Space: ?

Code

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        
        res = []
        def dfs(l, r, s):
            if l+r==0:
                res.append(''.join(s))
            if l>r:
                return
            if l>0:
                s.append('(')
                dfs(l-1,r,s)
                s.pop()
                
            if r>0:
                s.append(')')
                dfs(l,r-1,s)
                s.pop()
        dfs(n,n, [])
        
        return res