[leetcode] 22. Generate Parentheses

문제 설명

링크
n개 쌍의 () 를 활용하여 모든 가능한 parentheses 를 구하는 문제

접근

• backtracking 이용
• ( -> ( : ( 의 개수 < n, ) : 항상 가능
• ) -> ( : ( 의 개수 < n, ) : ) 의 개수 <= )의 개수

코드

    def generateParenthesis(self, n: int) -> List[str]:
        lenOfStr = n * 2
        ans = []

        def dfs(s: str, o: int, c: int):
            if len(s) == lenOfStr:
                ans.append(s)
                return
            if o < n:
                    dfs(s + '(', o + 1, c)
            if s[-1] == '(':    
                dfs(s + ')', o, c + 1)
            else:
                if o > c:
                    dfs(s + ')', o, c + 1)
        dfs('(', 1, 0)
        return ans