LeetCode: 22. Generate Parentheses

22. Generate Parentheses

LeetCode 22번 문제인 Generate Parentheses는 괄호((, ))를 사용하여 올바른 조합만 생성하는 대표적인 백트래킹 문제입니다.

문제 설명

입력으로 n이 주어지면, n 쌍의 괄호로 만들 수 있는
모든 잘 형성된(well-formed) 괄호 문자열을 반환해야 합니다.

예시

InputOutput

n = 1	["()"]
n = 3	["((()))","(()())","(())()","()(())","()()()"]

---

핵심 개념

올바른 괄호 문자열은 다음 조건을 만족합니다.

1. 여는 괄호 ( 개수는 n을 초과할 수 없다
2. 언제나 ) 개수 ≤ ( 개수 이어야 한다
   (닫는 괄호가 먼저 나오면 불가능)

즉, 생성 과정에서 잘못된 탐색을 조기에 차단하면
모든 경우를 탐색할 필요가 없습니다.
이것이 백트래킹의 가지치기 전략입니다.

---

✅ Java 구현 코드

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        if (n <= 0) return ans;
        dfs(n, 0, 0, new StringBuilder(), ans);
        return ans;
    }

    // n: 총 쌍 수, open: 사용한 '(' 개수, close: 사용한 ')' 개수
    private void dfs(int n, int open, int close, StringBuilder sb, List<String> out) {
        if (sb.length() == 2 * n) {
            out.add(sb.toString());
            return;
        }
        // '('을 더 사용할 수 있는 경우
        if (open < n) {
            sb.append('(');
            dfs(n, open + 1, close, sb, out);
            sb.deleteCharAt(sb.length() - 1);
        }
        // ')' 사용 시 '(' 보다 많아지면 안 됨
        if (close < open) {
            sb.append(')');
            dfs(n, open, close + 1, sb, out);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

---

📈 시간 및 공간 복잡도

이 문제는 카탈란 수 (Catalan Number)
CnC_nCn​ 개의 결과가 나옵니다.

• 시간 복잡도: O( Cn⋅nC_n \cdot nCn​⋅n )
• 공간 복잡도: O(n) (재귀 스택)

참고: C3=5,C4=14,C5=42C_3 = 5, C_4 = 14, C_5 = 42C3​=5,C4​=14,C5​=42
n이 커질수록 조합이 폭발적으로 증가합니다.