[리트코드] 22 - Generate Parentheses

22. Generate Parentheses

Medium

---

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

분류

문자열, 동적 계획법, 백트래킹, Bracket Sequences

---

문제 풀이

문제 분석

이 문제는 주어진 정수 n에 대해 n 쌍의 괄호로 만들 수 있는 모든 유효한 괄호 조합을 생성하는 문제입니다. 유효한 괄호 조합이란, 괄호의 열고 닫음이 올바르게 짝지어진 조합을 의미합니다. 예를 들어, n=3일 때 ((())), (()()), (())(), ()(()), ()()()와 같은 조합들을 생성해야 합니다.

입력은 정수 n (1 <= n <= 8)이며, 출력은 생성된 모든 유효한 괄호 조합을 문자열 리스트 형태로 반환합니다.

접근 방법

이 문제는 가능한 모든 조합을 탐색해야 하는 문제이므로, 백트래킹 (Backtracking) 기법을 사용하는 것이 매우 적합합니다. 백트래킹은 해를 탐색하는 과정에서, 현재 상태가 더 이상 유효한 해로 이어질 수 없다고 판단되면 해당 경로를 포기하고 이전 상태로 돌아가 다른 탐색을 진행하는 알고리즘입니다.

여기서는 재귀 함수(DFS)를 사용하여 괄호를 하나씩 추가하면서 유효한 괄호 조합을 만들어 나갑니다. 각 단계에서 열린 괄호 '(' 또는 닫힌 괄호 ')'를 추가할 수 있는지 여부를 판단하고, 가능한 경우에만 해당 괄호를 추가한 후 재귀적으로 다음 단계를 진행합니다.

구현 설명

코드는 DFS라는 재귀 함수를 사용하여 괄호 조합을 생성합니다.

1. 초기 상태 및 종료 조건 설정

• answer: 최종적으로 생성된 유효한 괄호 조합들을 저장할 리스트입니다.
• DFS 함수는 세 개의 인자를 받습니다:
  • stack: 현재까지 만들어진 괄호 문자열을 저장하는 리스트 (문자 하나씩 저장).
  • cnt: 현재까지 추가된 열린 괄호 '(' 와 닫힌 괄호 ')' 의 개수 차이. 즉, 닫힌 괄호 ')' 를 추가할 수 있는 횟수를 나타냅니다. cnt가 0이면 더 이상 닫힌 괄호를 추가할 수 없습니다.
  • level: 현재까지 만들어진 괄호 문자열의 총 길이. 목표 길이인 2 * n에 도달하면 탐색이 종료됩니다.
• 종료 조건: level이 2 * n과 같아지고, cnt가 0이 되면 (즉, 열린 괄호와 닫힌 괄호의 개수가 같아지면) 유효한 괄호 조합이 완성된 것이므로 answer 리스트에 추가합니다.

2. 닫힌 괄호 ')' 추가 조건 및 재귀 호출

• cnt > 0: 현재 cnt가 0보다 크다는 것은 아직 닫힌 괄호 ')' 를 추가할 여유가 있다는 의미입니다.
• stack.append(")"): 닫힌 괄호 ')' 를 stack에 추가합니다.
• DFS(stack, cnt - 1, level + 1): cnt를 1 감소시키고 level을 1 증가시켜 재귀 호출합니다. cnt를 감소시키는 이유는 닫힌 괄호를 하나 사용했기 때문입니다.
• stack.pop(): 백트래킹을 위해, 현재 재귀 호출에서 추가했던 닫힌 괄호 ')' 를 stack에서 제거합니다.

3. 열린 괄호 '(' 추가 조건 및 재귀 호출

• 2 * n - level > cnt: 이 조건은 매우 중요합니다. 2 * n은 최종 괄호 문자열의 총 길이이고, level은 현재까지의 길이입니다. 따라서 2 * n - level은 앞으로 추가해야 할 괄호의 남은 개수입니다. 이 남은 개수가 cnt (현재 열린 괄호가 닫힌 괄호보다 얼마나 더 많은지)보다 커야 한다는 것은, 앞으로 열린 괄호를 추가하더라도 최종적으로 닫힌 괄호를 모두 채울 수 있다는 것을 보장합니다. 즉, 과도한 열린 괄호로 인해 유효하지 않은 조합이 되는 것을 방지합니다.
• stack.append("("): 열린 괄호 '(' 를 stack에 추가합니다.
• DFS(stack, cnt + 1, level + 1): cnt를 1 증가시키고 level을 1 증가시켜 재귀 호출합니다. cnt를 증가시키는 이유는 열린 괄호를 하나 사용했기 때문입니다.
• stack.pop(): 백트래킹을 위해, 현재 재귀 호출에서 추가했던 열린 괄호 '(' 를 stack에서 제거합니다.

4. 최종 결과 반환

• DFS([], 0, 0): 초기 상태로 DFS 함수를 호출합니다. 빈 stack, cnt=0, level=0에서 시작합니다.
• return answer: 모든 탐색이 완료되면, answer 리스트에 저장된 유효한 괄호 조합들을 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(4^n / sqrt(n))
  • 이 문제의 시간 복잡도는 카탈란 수(Catalan Number)와 관련이 있습니다. 생성되는 유효한 괄호 조합의 수는 n번째 카탈란 수 C_n에 비례합니다.
  • 카탈란 수 C_n은 대략 O(4^n / n^(3/2))의 근사치를 가집니다.
  • 각 괄호 조합을 생성하는 과정에서 문자열을 붙이는 연산이 있지만, 전체적으로는 조합의 개수에 의해 지배됩니다.
• 공간 복잡도: O(n)
  • 재귀 호출의 최대 깊이는 2 * n입니다. 따라서 호출 스택의 깊이가 O(n)입니다.
  • stack에 저장되는 문자열의 최대 길이는 2 * n이므로 O(n)입니다.
  • 최종 answer 리스트에 저장되는 문자열들의 총 길이는 O(n * C_n)이지만, 일반적으로 공간 복잡도를 분석할 때는 재귀 호출 스택 깊이와 현재 사용되는 데이터 구조의 크기를 기준으로 합니다.

핵심 포인트

1. 백트래킹 활용: 유효한 괄호 조합을 효율적으로 탐색하기 위해 백트래킹 기법을 사용합니다. 각 단계에서 가능한 선택(열린 괄호 또는 닫힌 괄호 추가)을 시도하고, 유효하지 않은 경로를 조기에 포기합니다.
2. 유효성 조건: 열린 괄호와 닫힌 괄호를 추가할 수 있는 조건을 명확히 정의하는 것이 중요합니다.
   • 열린 괄호 '(': open_count < n (아직 열린 괄호를 n개 다 사용하지 않았을 때)
   • 닫힌 괄호 ')': close_count < open_count (닫힌 괄호의 개수가 열린 괄호의 개수보다 적을 때, 즉 짝을 이룰 수 있을 때)
   • (참고: 제공된 코드에서는 cnt와 level을 사용하여 이 조건을 간접적으로 표현했습니다. cnt > 0은 닫힌 괄호 추가 가능성을, 2*n - level > cnt는 열린 괄호 추가 시 최종적으로 닫힌 괄호를 모두 채울 수 있음을 보장합니다.)
3. 상태 관리: 재귀 호출 시 현재까지 만들어진 괄호 문자열(stack), 열린 괄호와 닫힌 괄호의 개수 차이(cnt), 그리고 현재 문자열의 길이(level)와 같은 상태를 정확하게 관리하고 백트래킹 과정에서 원상 복구하는 것이 핵심입니다.

풀이 코드

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        answer = []
        def DFS(stack, cnt, level):
            nonlocal answer

            if level == 2*n:
                if cnt == 0:
                    answer.append("".join(stack))
                    return

            if cnt > 0:
                stack.append(")")
                DFS(stack,cnt-1,level+1)
                stack.pop()

            if 2*n - level > cnt:
                stack.append("(")
                DFS(stack,cnt+1, level+1)
                stack.pop()
        
        DFS([],0,0)
        
        return answer