22. Generate Parentheses

22. Generate Parentheses

Medium

7848334Add to ListShare

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: ["()"]

 

Constraints:

• 1 <= n <= 8

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        
        res = []
        
        def dfs(cur, open_, close_):
            if open_==close_==n:
                res.append(cur)
                return
            
            if open_ < n:
                dfs(cur + "(", open_+1, close_)
            
            if open_ > close_:
                dfs(cur + ")", open_, close_+1)
            
        
        dfs("", 0, 0)
        
        return res

 

- 솔루션 참조.. 재귀에 대한 연습이 더 필요함