Pythonでリスト内の指定した合計になるトリプレット（3つの要素の組み合わせ）をすべて見つける方法

数値のリストの中から、3つの要素を組み合わせたときに特定の合計値になる組み合わせを探したいケースはよくあります。このような3つ組のことを「トリプレット（triplet）」と呼びます。1つのリストには、条件を満たすトリプレットが複数存在する場合があります。例えば、合計10は「1, 6, 3」でも「1, 5, 4」でも実現できます。

この記事では、Pythonを使って、与えられた数値のリストから条件を満たすすべてのトリプレットを見つける2つの方法を解説します。

方法1：rangeと一時変数を使う伝統的なアプローチ

まずは、ハッシュセット（set）と一時変数を活用する古典的な手法です。外側のループで1つ目の要素を固定し、内側のループで残りの2つの要素を効率よく探索します。「目標の合計 − 現在の2つの要素の和」に相当する値がすでにセットに存在するかどうかを確認することで、条件を満たすトリプレットを検出できます。この方法は計算量がO(n²)となり、総当たり方式よりも高速です。

サンプルコード

def SumTriplets(listA, sum):
    trpltcnt = 0
    res = []

    for i in range(0, len(listA) - 1):

        s = set()
        tmp = []

        # 1つ目の要素を追加
        tmp.append(listA[i])

        current_sum = sum - listA[i]

        for j in range(i + 1, len(listA)):

            if (current_sum - listA[j]) in s:
                trpltcnt += 1

                # 2つ目の要素を追加
                tmp.append(listA[j])

                # 3つ目の要素を追加
                tmp.append(current_sum - listA[j])

                # タプルとして最終結果のリストに追加
                res.append(tuple(tmp))
                tmp.pop(2)
                tmp.pop(1)
            s.add(listA[j])

    return res


listA = [11,12,13,14,15,16,17,18,19,20]

print("Required triplets:\n",SumTriplets(listA, 40))

実行結果

上記のコードを実行すると、次のような結果が得られます。

Required triplets:
[(11, 15, 14), (11, 16, 13), (11, 17, 12), (12, 15, 13)]

リスト [11〜20] の中から、合計が40になる4つのトリプレットが正しく抽出できていることがわかります。

方法2：itertools.combinationsを使うシンプルなアプローチ

次に、標準ライブラリ itertools の combinations 関数を利用する方法です。この関数は、リストから重複のない3つの要素の組み合わせをすべて生成してくれます。あとは filter() と組み合わせて、合計が目標値と一致する組み合わせだけを抽出します。

コードが非常に簡潔で読みやすくなるのがメリットですが、すべての組み合わせを生成してから絞り込むため、リストが大きくなると処理時間が増加する点には注意が必要です。

サンプルコード

from itertools import combinations

listA = [11,12,13,14,15,16,17,18,19,20]

def fsum(val):
    return sum(val) == 40

res = list(filter(fsum,list(combinations(listA, 3))))

print("Required triplets:\n",res)

実行結果

上記のコードを実行すると、次のような結果が得られます。

Required triplets:
[(11, 12, 17), (11, 13, 16), (11, 14, 15), (12, 13, 15)]

まとめ

どちらの方法でも同じ条件（合計40）に対して4つのトリプレットが見つかりました。ただし、両者の結果を見比べると、組み合わせが見つかる順序が異なります。これは、アルゴリズムの探索順序が違うためです。

• パフォーマンスを優先する場合： 大きなリストを扱うなら、ハッシュセットを活用した方法1（O(n²)）が有利です。
• 可読性・シンプルさを優先する場合： リストが小さい場合や、コードの分かりやすさが重要な場面では、itertoolsを使った方法2がおすすめです。

用途やデータサイズに応じて、適切な方法を選択してください。