【Python】バックトラッキングで有効な括弧の組み合わせをすべて生成する方法

問題の概要

整数 n が与えられたとき、開き括弧「(」と閉じ括弧「)」がそれぞれ n 個ずつ含まれる、すべての正しく対応した括弧の組み合わせを生成することを考えます。

例えば n = 3 の場合、生成される括弧のセットは次のようになります。

["()()()", "()(())", "(())()", "(()())", "((()))"]

ここで「正しく対応した」とは、任意の時点で閉じ括弧の数が開き括弧の数を超えず、最終的にすべての括弧が対応関係を持つ状態を指します。この問題は LeetCode の「Generate Parentheses」でもおなじみの、バックトラッキングの代表的な例題です。

解決アプローチ

この問題は再帰（バックトラッキング）を用いて解きます。基本的なアイデアは以下の通りです。

• generateParenthesisUtil() というメソッドを定義します。引数として、残りの開き括弧数 left、残りの閉じ括弧数 right、現在構築中の文字列 temp、そして結果を格納する配列 result を受け取ります。初期状態では result は空です。
• この関数は以下のように動作します。

1. left == 0 かつ right == 0 の場合：すべての括弧を使い切ったため、完成した文字列 temp を result に追加して処理を終了します。
2. left > 0 の場合：開き括弧がまだ残っているので、「(」を追加して再帰呼び出しを行います。
   generateParenthesisUtil(left - 1, right, temp + "(", result)
3. right > left の場合：閉じ括弧の方が多く残っているときだけ「)」を追加できます（これにより、未対応の開き括弧が必ず存在することが保証されます）。
   generateParenthesisUtil(left, right - 1, temp + ")", result)

Pythonでの実装例

実際のコードを見てみましょう。

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        result = []
        self.generateParenthesisUtil(n, n, "", result)
        return result

    def generateParenthesisUtil(self, left, right, temp, result):
        if left == 0 and right == 0:
            result.append(temp)
            return
        if left > 0:
            self.generateParenthesisUtil(left - 1, right, temp + '(', result)
        if right > left:
            self.generateParenthesisUtil(left, right - 1, temp + ')', result)

ob = Solution()
print(ob.generateParenthesis(4))

入力

4

出力

["(((())))",
"((()()))",
"((())())",
"((()))()",
"(()(()))",
"(()()())",
"(()())()",
"(())(())",
"(())()()",
"()((()))",
"()(()())",
"()(())()",
"()()(())",
"()()()()"]

仕組みのポイント

このアルゴリズムの核心は条件式 right > left にあります。開き括弧を追加すると left が減り、閉じ括弧を追加すると right が減るため、「残りの閉じ括弧数 ＞ 残りの開き括弧数」という状態は「文字列中にまだ閉じていない開き括弧が存在する」ことを意味します。この条件があることで、無効な文字列（例えば ")((" のようなもの）が生成されることを事前に防ぎ、探索木を大幅に枝刈りできます。

計算量についても触れておくと、有効な括弧の組み合わせの総数はカタラン数 C(2n, n) / (n + 1) で表され、時間計算量・空間計算量は O(4ⁿ / √n) 程度となります。