括弧の生成 (Generate Parentheses)

問題

n 組の括弧が与えられたとき、適切に閉じられた括弧のすべての組み合わせを生成する関数を作成する。

例

例 1

入力: n = 3
出力: ["((()))","(()())","(())()","()(())","()()()"]

例 2

入力: n = 1
出力: ["()"]

制約

1 <= n <= 8

解答 (Python)

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

        def backtrack(s, open_count, close_count):
            if len(s) == 2 * n:
                result.append(s)
                return

            if open_count < n:
                backtrack(s + "(", open_count + 1, close_count)

            if close_count < open_count:
                backtrack(s + ")", open_count, close_count + 1)

        backtrack("", 0, 0)
        return result

解説

初期化

result = []は有効な括弧の組み合わせをすべて格納するための空のリストである。

backtrack(s, open_count, close_count) 関数

これは括弧の文字列を構築する再帰的なヘルパー関数である。

• s: 現在構築中の括弧の文字列
• open_count: これまでに使用した開き括弧 '(' の数
• close_count: これまでに使用した閉じ括弧 ')' の数

ベースケース

if len(s) == 2 * nは現在の文字列 s の長さが 2 * n に等しい場合（つまり、n 個の開き括弧と n 個の閉じ括弧を使用した場合）、有効な組み合わせとなる。result.append(s)で有効な文字列 s を result リストに追加し、returnで有効な組み合わせが見つかったため、この分岐の再帰を停止する。

再帰ステップ

1. if open_count < n: これまでに使用した開き括弧の数が n より少ない場合、開き括弧をもう1つ追加できる。

   • backtrack(s + "(", open_count + 1, close_count): 再帰呼び出しを行い、現在の文字列 s に開き括弧を追加し、open_count をインクリメントし、close_count はそのままにする。

2. if close_count < open_count: これは括弧が適切に閉じられるようにするための重要な条件である。閉じ括弧を追加できるのは、これまでに使用した閉じ括弧の数が開き括弧の数よりも少ない場合のみである。これにより、))(( のような無効な組み合わせを防ぐ。

   • backtrack(s + ")", open_count, close_count + 1): 再帰呼び出しを行い、現在の文字列 s に閉じ括弧を追加し、open_count はそのままにし、close_count をインクリメントする。

初期呼び出し

backtrack("", 0, 0)は空の文字列 ""、開き括弧 0 個、閉じ括弧 0 個でバックトラック処理を開始する。

適切に閉じられた括弧を保証する方法

開き括弧の追加

まだ n 個すべての開き括弧を使用していない限り、開き括弧を追加できる（open_count < n）。

閉じ括弧の追加

閉じ括弧を追加できるのは、これまでに使用した開き括弧の数が、これまでに使用した閉じ括弧の数よりも多い場合のみである（close_count < open_count）。これにより、文字列のどの時点においても閉じ括弧の数が開き括弧の数を超えることがないようにする。これは適切に閉じられた括弧の核となる要件である。

ベースケース

文字列の長さが 2 * n になった場合にのみ、その文字列を結果に追加する。これにより、n 個の開き括弧と n 個の閉じ括弧がすべて使用されていることが保証される。

例の分解 (n = 3)

1. backtrack("", 0, 0)
   * backtrack("(", 1, 0)
      * backtrack("((", 2, 0)
         * backtrack("(((", 3, 0)
            * backtrack("((()", 3, 1)
               * backtrack("((())", 3, 2)
                  * backtrack("((()))", 3, 3) -> result.append("((()))")
            * backtrack("(()", 2, 1)
               * backtrack("(()(", 3, 1)
                  * backtrack("(()()", 3, 2)
                     * backtrack("(()())", 3, 3) -> result.append("(()())")
               * backtrack("(())", 2, 2)
                  * backtrack("(())", 2, 2)
                     * backtrack("(())", 2, 2)
                        * backtrack("(())()", 2, 3) -> result.append("(())()")
      * backtrack("()", 1, 1)
         * backtrack("()(", 2, 1)
            * backtrack("()((", 3, 1)
               * backtrack("()(()", 3, 2)
                  * backtrack("()(())", 3, 3) -> result.append("()(())")
            * backtrack("()()", 2, 2)
               * backtrack("()()", 2, 2)
                  * backtrack("()()", 2, 2)
                     * backtrack("()()()", 2, 3) -> result.append("()()()")

再帰は各ステップで開き括弧または閉じ括弧を追加する選択を行うことによって、すべての有効な組み合わせを探索する。そして、条件によって、生成される文字列が常に適切に閉じられていることが保証される。