[LeetCode] 22. Generate Parentheses

접근

• 기본적인 백트래킹 문제, 문제 조건이 크게 까다롭지 않아 브루트 포스로 풀 수도 있지만 백트래킹 방법이 출제 의도인 것 같음
• 문제의 해답이 될 수 있는 경우에 대한 경우를 일반화해야 함. 여기서 막혔음
• 자연스럽게 중간에 오답이 되는 케이스는 흘려 보내는 논리 흐름이 백트래킹의 핵심
• 스택이 아닌 변수를 활용하여 괜찮은 솔루션을 작성할 수 있음 

 

솔루션

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        answer = []

        def backtracking(answer_str, left, right):
            # if it reach to the end, add answer 
            if len(answer_str) == n*2:
                answer.append(answer_str)
                return
            
            # first, we have to check whether can add more '('
            if left < n:
                backtracking(answer_str + '(', left+1, right)

            # second, if we can add more ')' add it
            if right < left:
                backtracking(answer_str + ')', left, right+1)
        
        backtracking("", 0, 0)

        return answer