Pythonで部分集合（冪集合）をすべて生成する方法を解説

はじめに

ある数値の集合が与えられたとき、その集合から作れるすべての部分集合を生成する問題を考えてみましょう。この「すべての部分集合の集まり」は冪集合（べきしゅうごう、Power Set）と呼ばれます。

例えば、集合が [1, 2, 3] の場合、冪集合は次のようになります。

[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

要素数が n の集合に対して部分集合は 2ⁿ 個存在するため、n = 3 なら 8 個の部分集合が得られます。

アルゴリズムの考え方：再帰による解法

この問題は再帰（バックトラッキング）を使って elegantly 解くことができます。基本的なアイデアは、各要素について「部分集合に含める（1）」か「含めない（0）」かを選択しながら、すべての組み合わせを探索するというものです。

手順の概要

• 再帰関数 solve() を定義します。引数は数値リスト（nums）、一時フラグ配列（temp）、結果格納用リスト（res）、現在のインデックス（index）です。
• solve() の動作は以下の通りです。
• 終了条件： index が nums の長さに達したら、temp のコピーを作成して res に追加し、処理を終了します。
• temp[index] = 0 を設定し（要素を選ばない場合）、solve(nums, temp, res, index + 1) を呼び出します。
• temp[index] = 1 を設定し（要素を選ぶ場合）、再度 solve(nums, temp, res, index + 1) を呼び出します。

メイン関数の流れ

• 空の結果リスト res を用意する。
• nums と同じサイズの temp リストを作成し、0 で初期化する。
• solve(nums, temp, res, 0) を呼び出す。
• temp_res 内の各リスト（0/1 フラグ列）に対して以下を繰り返す。
  • 空の一時リスト temp を作成。
  • i を 0 からリストの長さまで走査し、lists[i] == 1 なら nums[i] を temp に追加。
  • 完成した temp を main_res に追加。
• main_res を返す。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution(object):
    def subsets(self, nums):
        temp_result = []
        self.subsets_util(nums, [0 for i in range(len(nums))], temp_result, 0)
        main_result = []
        for lists in temp_result:
            temp = []
            for i in range(len(lists)):
                if lists[i] == 1:
                    temp.append(nums[i])
            main_result.append(temp)
        return main_result

    def subsets_util(self, nums, temp, result, index):
        if index == len(nums):
            result.append([i for i in temp])
            return
        temp[index] = 0
        self.subsets_util(nums, temp, result, index + 1)
        temp[index] = 1
        self.subsets_util(nums, temp, result, index + 1)

ob1 = Solution()
print(ob1.subsets([1, 2, 3, 4]))

入力

[1, 2, 3, 4]

出力

[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4],
 [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4],
 [1, 2, 3], [1, 2, 3, 4]]

計算量について

このアプローチでは、各要素ごとに「含める／含めない」の2択があるため、時間計算量は O(2ⁿ) となります。また、各部分集合を格納するため、空間計算量も O(2ⁿ) です。これは冪集合の性質上避けられないコストですが、再帰構造によりコードは非常にシンプルで理解しやすくなっています。

まとめ

本記事では、再帰的なバックトラッキングを用いて、与えられた集合のすべての部分集合（冪集合）を生成する方法を紹介しました。0/1 フラグ配列で各要素の選択状態を管理することで、直感的かつ効率的に全組み合わせを列挙できます。同様の手法は、順列・組み合わせ生成など、他の組み合わせ探索問題にも応用できます。