以下は generateParenthesis の処理を、 図を用いて具体的に解析・説明した内容です。
n個の括弧の組み合わせから「正しい組み合わせだけ」を出力する問題。
全ての正しい括弧の組み合わせ：
((()))
(()())
(())()
()(())
()()()
current = ""
open = 3
close = 3
- 「(」はまだ残っていれば追加可能
- 「)」は、現在使った「(」より多くは使えない
""
/ \
( ×
"("/ \
/ \
"((" "()"
/ \ \
"(((" "(()" "()("
| / \ \
"((()" "(()(" "(())" "()()"
| | | \
"((())" "(()()" "(())(" "()()("
| | | \
"((()))" "(()())" "(())()" "()()()"
| ノード | 意味 |
|---|---|
"(((" |
開き括弧3つ追加。閉じ括弧はまだ使えない。 |
"(()" |
開き括弧2つ、閉じ括弧1つ。 |
"(()())" |
完成パターン（正しい） |
"((()))" |
完成パターン（正しい） |
"()()()" |
完成パターン（正しい） |
| current | 現在構築中の文字列 |
|---|---|
| open | 残り使える「(」の数 |
| close | 残り使える「)」の数 |
open > 0→ 「(」を追加close > open→ 「)」を追加（ただし「(」の数より多くは使えない）
current = "(" → OK （open > 0）
current = "()" → OK （close > open）
current = ")(" → NG！（無視）← 不正な場合は探索しない
| current | open | close | |
|---|---|---|---|
| "" | 3 | 3 | |
| "(" | 2 | 3 | |
| "((" | 1 | 3 | |
| "(()" | 1 | 2 | |
| "(()(" | 0 | 2 | |
| "(()()" | 0 | 1 | |
| "(()())" | 0 | 0 | ✅ 完成！ |
カタラン数 Cn：
例：
| n | 組み合わせ数 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
| 5 | 42 |
| 6 | 132 |
| 7 | 429 |
| 8 | 1430 |
| 項目 | 計算量 |
|---|---|
| 時間計算量 | O(4^n / √n) |
| 空間計算量 | O(4^n / √n) |
理由： 「全ての正しい括弧の組み合わせ」の個数＝カタラン数 → O(4^n / √n)
| 項目 | 内容 |
|---|---|
| 効率性 | 不要な組み合わせを生成しない（枝刈り） |
| シンプルさ | 再帰＋状態管理のみ |
| メモリ | 結果＋再帰スタックだけ使用 |
開始 → ( または ) を選択しながら再帰探索
└─ 「全ての開き括弧を使ったか？」
└─ YES: 閉じ括弧だけ追加可能
└─ NO: ( と ) の両方試す（ただし「)」はopen < close）
└─ 完成したら result に追加