LeetCode

LeetCode 22 Generate Parentheses 풀이: 유효한 접두사만 만드는 백트래킹

2026년 10월 22일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 22. Generate Parentheses
출처: LeetCode
학습: 백트래킹 학습 가이드
자체 판단 난이도: Level 3

각 위치에서 괄호를 선택해 답을 생성하고, 현재까지의 문자열이 더는 유효해질 수 없으면 그 분기를 중단해야 한다. 선택 조건과 재귀 후 상태 복원을 정확히 관리해야 하므로 Level 3으로 판단했다.

문제 원문과 제한 조건은 바뀔 수 있으므로 제출 전에 공식 문제 페이지를 다시 확인한다.

1. 문제 요약

괄호 n쌍으로 만들 수 있는 모든 올바른 괄호 문자열을 생성한다. 올바른 문자열은 여는 괄호와 닫는 괄호의 짝이 맞고, 문자열을 왼쪽부터 읽는 어느 시점에서도 닫는 괄호가 여는 괄호보다 많아지지 않아야 한다.

문제의 조건은 다음과 같다.

n은 1 이상 8 이하이다.
결과에는 여는 괄호 n개와 닫는 괄호 n개가 각각 들어간다.
반환되는 문자열의 순서는 제한되지 않는다.

예를 들어 n = 3이면 ((())), (()()), (())(), ()(()), ()()()의 다섯 문자열을 반환한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

접두 문자열에서 지켜야 하는 불변식

현재까지 고른 여는 괄호 수를 open_count, 닫는 괄호 수를 close_count라고 하자. 모든 탐색 단계에서 다음 조건을 유지한다.

0 <= close_count <= open_count <= n

open_count <= n은 여는 괄호를 필요한 수보다 많이 쓰지 않게 하고, close_count <= open_count는 닫는 괄호가 아직 짝을 찾지 못한 여는 괄호보다 많아지는 것을 막는다. 특히 두 번째 조건은 접두 문자열이 이미 잘못된 순간 해당 경로를 즉시 제외하게 한다.

이 조건을 지키면 open_count == close_count == n에 도달했을 때 모든 괄호를 사용한 올바른 문자열이므로 결과에 추가한다.

두 선택 조건이 모든 답을 정확히 만든다

현재 상태에서 가능한 다음 문자는 두 가지 규칙으로 결정된다.

아직 여는 괄호를 n개 다 쓰지 않았다면 (를 추가한다.
짝이 맞지 않은 여는 괄호가 남아 있다면, 즉 close_count < open_count이면 )를 추가한다.

모든 올바른 문자열은 어느 접두사에서도 close_count <= open_count를 만족하므로, 이 두 규칙은 정답이 될 문자열의 선택을 차단하지 않는다. 반대로 각 선택을 문자 순서대로 한 번씩만 따라가므로 같은 문자열을 여러 경로에서 만들지도 않는다.

n = 3에서 ((()))가 만들어지는 한 경로는 다음과 같다.

현재 경로	여는 수	닫는 수	가능한 선택
빈 문자열	0	0	`(`
`(`	1	0	`(` 또는 `)`
`((`	2	0	`(` 또는 `)`
`(((`	3	0	`)`
`((()`	3	1	`)`
`((())`	3	2	`)`
`((()))`	3	3	결과에 저장

잘못된 분기를 생성하지 않는 이유

완성된 길이 2n의 문자열을 전부 만든 뒤 유효한지 검사하면 후보마다 다시 왼쪽부터 균형을 확인해야 한다. n = 3에서는 2^6 = 64개 후보 중 올바른 문자열은 5개뿐이다. 현재 접두사가 유효한 경우에만 다음 문자를 붙이면 유효하지 않은 접두사 아래의 모든 후속 후보를 만들지 않아도 된다.

닫는 괄호의 조건을 단순히 close_count < n으로 두는 것도 틀린다. 아직 여는 괄호가 하나도 없는 시작 상태에서도 )를 붙일 수 있어 )( 같은 잘못된 접두사가 만들어진다. 닫을 수 있는지는 전체 닫는 수가 아니라 아직 닫히지 않은 여는 괄호가 있는지로 판단해야 한다.

시간·공간 복잡도

반환해야 할 문자열 수는 n번째 카탈란 수 C_n = (1 / (n + 1)) × binom(2n, n)이다. 각 결과 문자열 길이는 2n이고, 각 결과를 문자열로 합치는 데 O(n)이 필요하다. 결과 저장까지 포함한 시간 복잡도는 O(n × C_n), 반환 결과 공간도 O(n × C_n)이다.

현재 경로와 재귀 호출 스택은 최대 길이 2n만큼 유지하므로 결과를 제외한 보조 공간은 O(n)이다.

3. 문제 해결 코드 (Python)

path에는 현재 접두 문자열의 문자만 저장한다. 재귀 호출 후 방금 추가한 문자를 pop()해 선택 전 상태로 복원하고, 완성된 문자열에서만 "".join(path)로 결과 문자열을 만든다.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []
        path = []

        def backtrack(open_count: int, close_count: int) -> None:
            if open_count == n and close_count == n:
                result.append("".join(path))
                return

            if open_count < n:
                path.append("(")
                backtrack(open_count + 1, close_count)
                path.pop()

            if close_count < open_count:
                path.append(")")
                backtrack(open_count, close_count + 1)
                path.pop()

        backtrack(0, 0)
        return result

close_count < open_count일 때만 닫는 괄호를 붙이므로 잘못된 접두 문자열은 생성되지 않는다. 각 재귀 호출이 끝난 뒤 path.pop()을 실행해야 다른 분기가 직전 선택을 물려받지 않는다.

복사해 실행할 테스트

반환 순서는 정해져 있지 않으므로 공식 예제는 집합과 개수로 비교한다. 최대 입력에서는 결과 개수와 고유성, 모든 문자열의 유효성을 함께 확인한다.

def is_well_formed(text):
    balance = 0
    for char in text:
        balance += 1 if char == "(" else -1
        if balance < 0:
            return False
    return balance == 0


example = Solution().generateParenthesis(3)
expected = {"((()))", "(()())", "(())()", "()(())", "()()()"}
assert set(example) == expected
assert len(example) == len(expected)

assert Solution().generateParenthesis(1) == ["()"]
assert set(Solution().generateParenthesis(2)) == {"(())", "()()"}

largest = Solution().generateParenthesis(8)
assert len(largest) == 1430
assert len(set(largest)) == 1430
assert all(len(item) == 16 and is_well_formed(item) for item in largest)

4. 공식 예제와 추가 검증

generateParenthesis를 Python으로 실행했다. 공식 예제 두 개, 작은 입력, 최대 제한 입력에서 결과 개수와 중복 여부를 확인했다.

공식 예제 1

입력: n = 3
기대 출력: ["((()))", "(()())", "(())()", "()(())", "()()()"] (순서 무관)
실행 결과: 통과
검증 목적: 가능한 다섯 올바른 문자열을 빠짐없이 한 번씩 생성하는지 확인

공식 예제 2

입력: n = 1
기대 출력: ["()"]
실행 결과: 통과
검증 목적: 가장 작은 허용 입력의 단일 결과 확인

추가 검증: n = 2

입력: n = 2
기대 출력: {"(())", "()()"}
실행 결과: 통과
검증 목적: 닫는 괄호 선택을 허용하는 시점과 문자열 개수 확인

추가 검증: 최대 n = 8

입력: n = 8
기대 결과: 길이 16인 고유한 올바른 문자열 1,430개
실행 결과: 통과
검증 목적: 최대 제약에서 결과 개수, 중복 없음, 모든 접두 균형 유지 확인

5. 다른 풀이 방식 검색 및 비교

Generate Parentheses 공식 문제는 n쌍으로 만들 수 있는 모든 올바른 괄호 문자열을 요구한다.
NeetCode의 Generate Parentheses 설명은 모든 문자열을 만든 뒤 검사하는 방법과, 유효한 선택만 확장하는 백트래킹을 비교한다.

완성된 길이 2n 문자열을 모두 생성한 뒤 검사하는 방법은 구현이 직관적이지만 2^(2n)개의 후보마다 최대 O(n) 검사가 필요해 O(n × 2^(2n)) 시간이 든다. 이 글의 백트래킹은 close_count <= open_count를 깨는 순간 가지를 자르고, 실제로 반환할 카탈란 수만큼의 결과만 완성한다.

마무리

Generate Parentheses의 핵심은 괄호 문자열을 다 만든 뒤 잘못된 결과를 거르는 것이 아니라, 유효한 접두 문자열만 이어 붙이는 것이다. open_count < n이면 여는 괄호를 추가하고, close_count < open_count이면 닫는 괄호를 추가한다. 이 두 조건과 재귀 후 상태 복원이 모든 올바른 문자열을 중복 없이 만든다.