【Python】動的計画法で合計がkになる組み合わせの数を求める方法

重複のない整数のリスト nums と、ある数値 k が与えられたとき、要素の合計がちょうど k になる組み合わせが何通り存在するかを求めます。なお、組み合わせを作る際には、同じ数字を何度でも繰り返し使って構いません。

たとえば、入力が nums = [2, 4, 5]、k = 4 の場合、出力は 2 になります。[2, 2] と [4] の2通りの作り方が存在するためです。

解法のアプローチ(動的計画法)

この問題は、いわゆる「コイン両替問題」と同型で、動的計画法(DP)を使うことで効率的に解けます。考え方の手順は以下の通りです。

• サイズが k+1 のリスト table を用意し、すべて 0 で初期化する
• table[0] := 1 とする(合計 0 を作る方法は「何も選ばない」の1通りだけ)
• nums の各 num について、以下を繰り返す
  • i が num から k までの範囲で、table[i] := table[i] + table[i - num] を実行する
• 最後に table[k] を返す

ここで重要なのは、数字ごとの外側ループ・合計額の内側ループという順序にすることです。この順序により「[2, 4] と [4, 2]」のような順列の重複が排除され、組み合わせだけが正しくカウントされます。

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

サンプルコード

class Solution:
    def solve(self, nums, k):
        table = [1] + [0] * k

        for num in nums:
            for i in range(num, k + 1):
                table[i] += table[i - num]

        return table[k]

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

入力

[2, 4, 5], 4

出力

2

処理の流れを追ってみる

num = 2 を処理した時点で table は [1, 0, 1, 0, 1](2だけで作れる合計のパターン)となり、続いて num = 4 を処理すると table[4] に [4] 単体のパターンが加わって 2 になります。num = 5 は k = 4 より大きいため影響しません。

計算量

時間計算量は O(n × k)(n は nums の要素数)、空間計算量は O(k) です。全組み合わせを総当たりする指数時間の探索と比べ、非常に効率的に答えを求められます。