Pythonで合計が特定の値になるすべてのサブセット（部分集合）を取得する方法

プログラミングでは、リストの中から「合計が特定の値 s になる」すべてのサブセット（部分集合）を見つけたい場面があります。本記事では、Pythonの標準ライブラリ itertools の combinations 関数を使って、この問題をシンプルかつ確実に解決する方法を解説します。

基本的なアプローチは次のとおりです。まずリストの長さごとにすべての組み合わせを生成し、それぞれの合計が目標値と一致するかどうかを判定します。一致した組み合わせだけをコンソールに出力します。

サンプルコード

以下は、実際に動作する完全なコード例です。

from itertools import combinations

def sub_set_sum(size, my_array, sub_set_sum):

    for i in range(size+1):
        for my_sub_set in combinations(my_array, i):

            if sum(my_sub_set) == sub_set_sum:
                print(list(my_sub_set))

my_size = 6
my_list = [21, 32, 56, 78, 45, 99, 0]
print("The list is :")
print(my_list)
subset_sum = 53
print("The result is :")
sub_set_sum(my_size, my_list, subset_sum)

実行結果

The list is :
[21, 32, 56, 78, 45, 99, 0]
The result is :
[21, 32]
[21, 32, 0]

この例では、目標値を 53 としています。その結果、「21 + 32 = 53」となる [21, 32] と、0 を加えても合計が変わらないため有効となる [21, 32, 0] の2つのサブセットが出力されました。

コードの解説

• まず、itertools モジュールから combinations をインポートします。これは指定した要素数のすべての組み合わせを生成する便利な関数です。

• sub_set_sum という名前の関数を定義します。引数にはリストのサイズ、対象となるリスト、そして目標となる合計値を受け取ります。

• 外側のループ for i in range(size+1) により、組み合わせの要素数を1個から順に変化させながら反復処理を行います。size+1 としているのは、最大でリスト全体を選ぶパターンも含めるためです。

• 内側のループで combinations(my_array, i) を呼び出し、要素数 i のすべての組み合わせを取得します。

• sum() 関数で各組み合わせの合計を計算し、目標値と一致した場合のみ、タプルを list() でリストに変換してコンソールに出力します。

• 関数の外部では、リストのサイズ、対象リスト、そして目標となるサブセットの合計値をそれぞれ定義し、リストの内容を表示しています。

• 最後に、必要な引数を渡して関数を呼び出すことで、条件を満たすすべてのサブセットが出力されます。

補足：パフォーマンスに関する注意点

combinations を使うこの手法は直感的で理解しやすい一方、組み合わせの総数はリストのサイズ n に対して 2ⁿ に近い規模で増加します。そのため、要素数が多いリストに対しては計算時間が急激に伸びる点に注意が必要です。小〜中規模のデータであれば十分実用的ですが、大規模データや高速化が必要なケースでは、動的計画法（DP）などを用いた「部分和問題」向けのアルゴリズムを検討するとよいでしょう。