Pythonで合計がkになる部分集合の個数を数えるプログラム

数値のリスト nums と整数 k が与えられたとき、リストの要素から作れる部分集合（サブセット）のうち、合計がちょうど k になるものの個数を求めます。答えが非常に大きくなる可能性があるため、結果は 10⁹ + 7 で割った余りを返します。

たとえば、入力が nums = [2, 3, 4, 5, 7]、k = 7 の場合、出力は 3 になります。[2, 5]、[3, 4]、[7] の 3 つの部分集合が条件を満たすためです。

解法のアプローチ：動的計画法（DP）

この問題はナップサック問題と同じ構造を持っており、動的計画法を使うことで効率的に解けます。dp[j] を「合計が j になる部分集合の個数」と定義し、各要素を順番に処理しながら DP テーブルを更新していきます。

アルゴリズムの手順

• サイズ (k + 1) のリスト dp を作成し、すべて 0 で初期化します。
• dp[0] := 1 とします。何も選ばない空の部分集合で合計 0 が作れるのは 1 通りだからです。
• m := 10^9 + 7 とします（剰余を取るための定数）。
• i を 0 から nums の長さ - 1 まで繰り返します。
  • j を k から 0 まで 1 ずつ減らしながら繰り返します。
    • nums[i] <= j の場合：
      • dp[j] := dp[j] + dp[j - nums[i]]
      • dp[j] := dp[j] mod m
• 最後に dp[k] mod m を返します。

なぜ j を降順にループするのか？

内側のループを k から 0 に向かって降順に回すのが重要なポイントです。もし昇順に処理すると、同じ要素を何度も使ってしまうため正しい答えが得られません。降順にすることで、各要素がそれぞれ 1 回だけ使われることが保証されます。

実装例

class Solution:
    def solve(self, nums, k):
        dp = [0] * (k + 1)
        dp[0] = 1
        m = int(1e9 + 7)
        for i in range(len(nums)):
            for j in range(k, -1, -1):
                if nums[i] <= j:
                    dp[j] += dp[j - nums[i]]
                    dp[j] %= m
        return dp[k] % m

ob = Solution()
nums = [2, 3, 4, 5, 7]
k = 7
print(ob.solve(nums, k))

入力

[2, 3, 4, 5, 7], 7

出力

3

計算量

時間計算量は O(n × k)、空間計算量は O(k) です（n は nums の要素数）。すべての部分集合を列挙する O(2ⁿ) の総当たり法と比べて、大幅に効率化できることがわかります。