[Leetcode/파이썬] 22. Generate Parentheses

Generate Parentheses

---

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:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(left, right, s) :
            if len(s) == n * 2 :
                res.append(s)
                return

            if left < n :
                dfs(left + 1, right, s + '(')

            if right < left :
                dfs(left, right + 1, s + ')')
                
        res = []
        dfs(0, 0, '')
        return res

다른 분의 코드를 참고하였다. 

오랜만에 보는 백트래킹 문제라 문제를 백트래킹으로 풀어야지라고 바로 떠올리지 못했다. 이 문제는 나중에 디버깅 하면서 다시 풀어봐야겠다.