Pythonでコインの種類と所持数量から作れる合計金額のパターン数を求める方法

問題の概要

コインの額面を格納したリスト coins と、それぞれのコインの所持数量を格納したリスト quantities が与えられます。2つのリストは同じ長さを持ち、i番目のコインの額面は coins[i]、その所持数は quantities[i] です。

このとき、これらのコインを1枚以上使用して作り出せる「異なる合計金額」の個数を求めるのが本問題の目的です。

具体例

入力が以下の場合を考えてみましょう。

• coins = [1, 2, 5]
• quantities = [1, 2, 1]

この場合、出力は 10 になります。作り出せる合計金額は次の10通りです。

• [1] → 1
• [2] → 2
• [1, 2] → 3
• [2, 2] → 4
• [5] → 5
• [1, 5] → 6
• [2, 5] → 7
• [1, 2, 5] → 8
• [2, 2, 5] → 9
• [1, 2, 2, 5] → 10

解法のアプローチ

この問題は再帰（バックトラッキング）を使って解くことができます。各コインについて「0枚から所持数量まで」の範囲で使用枚数を全通り試し、そのたびに合計値を集合に記録していきます。

アルゴリズムの手順

1. 再帰関数 rec(i, res) を定義します。ここで i は現在処理中のコインのインデックス、res はそれまでの合計値です。
2. i がコインの総数と等しくなったら、再帰を終了します。
3. k を 0 から quantities[i] までループさせ、cur = res + k * coins[i] を計算します。
4. cur を結果用の集合 fres に追加し、rec(i + 1, cur) を呼び出します。
5. メイン処理では空の集合を作成し、rec(0, 0) を実行します。
6. 最後に fres のサイズから 1 を引いた値を返します（0円のケースを除外するため）。

実装コード

class Solution:
    def solve(self, coins, quantities):
        def rec(i, res):
            if i == len(coins):
                return
            for k in range(0, quantities[i] + 1):
                cur = res + k * coins[i]
                fres.add(cur)
                rec(i + 1, cur)

        fres = set()
        rec(0, 0)
        return len(fres) - 1

ob = Solution()
coins = [1, 2, 5]
quantities = [1, 2, 1]
print(ob.solve(coins, quantities))

入力

[1, 2, 5], [1, 2, 1]

出力

10

解説のポイント

この実装における重要なポイントは以下の通りです。

• 重複の排除： 合計値を set（集合）に格納することで、同じ金額が複数回カウントされるのを自動的に防げます。
• -1 の理由： 再帰の初期状態として 0 円（何も選んでいない状態）も集合に含まれるため、問題の条件である「非空のグループ」に該当しない 0 を除外するためにサイズから 1 を引いています。
• 計算量： 各コインについて最大 quantities[i] + 1 通りの選択肢があるため、計算量は O(Π(quantities[i]+1)) となります。数量が大きい場合は動的計画法（DP）による最適化も検討できます。