Pythonでサブセット和問題（部分和問題）を解く方法｜再帰と動的計画法の実装例

本記事では、以下の問題設定に対する解法を段階的に学んでいきます。

問題の定義

問題文： 負でない整数からなる配列（集合）と目標値 sum が与えられます。このとき、与えられた集合の部分集合のうち、その要素の合計が sum と一致するものが存在するかどうかを判定してください。

それでは、実際の実装を見ながら解法を確認していきましょう。

素朴なアプローチ（再帰）

最も直感的な方法は、各要素について「部分集合に含める」か「含めない」かの2択をすべて試す再帰的な探索です。最後の要素が sum より大きい場合は無視でき、それ以外の場合は「含める場合」と「含めない場合」のどちらか一方でも成功すれば True を返します。

def SubsetSum(set, n, sum):
    # ベースケース
    if (sum == 0):
        return True
    if (n == 0 and sum != 0):
        return False
    # 最後の要素が sum より大きい場合は無視する
    if (set[n - 1] > sum):
        return SubsetSum(set, n - 1, sum)
    # それ以外の場合、次の2通りを確認する
    # (1) 最後の要素を含める場合
    # (2) 最後の要素を含めない場合
    return SubsetSum(set, n - 1, sum) or SubsetSum(set, n - 1, sum - set[n - 1])

# メイン処理
set = [2, 14, 6, 22, 4, 8]
sum = 10
n = len(set)
if (SubsetSum(set, n, sum) == True):
    print("Found a subset with given sum")
else:
    print("No subset with given sum")

出力

Found a subset with given sum

この例では、{2, 8} や {6, 4} といった部分集合の合計が 10 になるため、「見つかった」と判定されます。

ただし、この再帰的なアプローチでは同じ状態を繰り返し計算してしまうため、最悪の場合の時間計算量は O(2ⁿ) となり、要素数が増えると非現実的に遅くなります。

動的計画法によるアプローチ

計算量の問題を解決するために、動的計画法（DP）を利用します。dp[i][j] を「先頭から i 個の要素の中から部分集合を選び、合計を j にできるか」と定義することで、重複する計算を表に記録しながら効率よく答えを求められます。時間計算量は O(n × sum)、空間計算量も同様に O(n × sum) です。

# 動的計画法によるサブセット和問題の解法
def isSubsetSum(set, n, sum):
    # dp[i][j]: 先頭 i 個の要素で和 j を作れるかどうか
    dp = [[False for _ in range(sum + 1)] for _ in range(n + 1)]

    # 和が 0 の場合は空集合を選べばよいため常に True
    for i in range(n + 1):
        dp[i][0] = True

    # 表を順に埋めていく
    for i in range(1, n + 1):
        for j in range(1, sum + 1):
            if set[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - set[i - 1]]

    return dp[n][sum]

# メイン処理
set = [2, 14, 6, 22, 4, 8]
sum = 10
n = len(set)
if (isSubsetSum(set, n, sum)):
    print("Found a subset with given sum")
else:
    print("No subset with given sum")

出力

Found a subset with given sum

まとめ

本記事では、サブセット和問題（部分和問題）をPythonで解く2つの方法を紹介しました。シンプルな再帰による解法は理解しやすい一方で計算量が大きく、動的計画法を用いることで O(n × sum) まで効率化できることを確認しました。サブセット和問題はナップサック問題など多くの応用問題の基礎となる重要なトピックなので、ぜひマスターしておきましょう。