22. Generate Parentheses

22. Generate Parentheses

 

https://youtu.be/s9fokUqJ76A?si=ERC4z90YXz3-fkws

 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # stack: 현재까지 생성된 괄호를 저장하는 스택
        # res: 유효한 괄호 조합을 저장할 결과 리스트
        stack = []
        res = []

        # 백트래킹 함수 정의
        def backtrack(openN, closedN):
            # openN: 열린 괄호 '('의 개수
            # closedN: 닫힌 괄호 ')'의 개수

            # 베이스 케이스: 열린 괄호와 닫힌 괄호의 개수가 모두 n일 때
            if openN == closedN == n:
                res.append("".join(stack))  # 스택에 저장된 괄호를 문자열로 변환하여 결과에 추가
                return

            # 열린 괄호를 추가할 수 있는 조건: 열린 괄호의 개수가 n보다 작을 때
            if openN < n:
                stack.append("(")  # 열린 괄호 '(' 추가
                backtrack(openN + 1, closedN)  # 열린 괄호 개수를 증가시키고 재귀 호출
                stack.pop()  # 백트래킹: 마지막으로 추가한 '(' 제거

            # 닫힌 괄호를 추가할 수 있는 조건: 닫힌 괄호의 개수가 열린 괄호보다 작을 때
            if closedN < openN:
                stack.append(")")  # 닫힌 괄호 ')' 추가
                backtrack(openN, closedN + 1)  # 닫힌 괄호 개수를 증가시키고 재귀 호출
                stack.pop()  # 백트래킹: 마지막으로 추가한 ')' 제거

        # 탐색 시작: 열린 괄호와 닫힌 괄호의 개수를 0으로 초기화
        backtrack(0, 0)

        # 생성된 모든 유효한 괄호 조합을 반환
        return res

 

상세 설명

1. stack과 res:
   • stack은 현재까지 구성된 괄호 조합을 저장합니다.
   • res는 유효한 괄호 조합을 저장하는 최종 결과 리스트입니다.
2. backtrack(openN, closedN):
   • openN: 현재까지 추가된 열린 괄호의 개수.
   • closedN: 현재까지 추가된 닫힌 괄호의 개수.

 

백트래킹의 핵심

• 열린 괄호와 닫힌 괄호를 조건에 맞게 추가하며 가능한 조합을 탐색.
• 조건에 맞지 않는 조합은 탐색하지 않음으로써 효율적으로 모든 경우를 생성.
• 백트래킹을 통해 탐색을 마친 뒤 상태를 복구.