Pythonで配列の要素を繰り返し使って指定した合計値を作れるか判定する方法

nums という配列ともうひとつの値 sum が与えられたとします。このとき、nums に含まれる要素を足し合わせて sum を作ることができるかどうかを判定します。なお、同じ要素は何度でも選んでよいものとします。

たとえば、入力が nums = [2, 3, 5]、sum = 28 の場合、出力は True になります。これは 5 + 5 + 5 + 5 + 3 + 3 + 2 = 28 という組み合わせで合計を作れるためです。

解法のアプローチ

この問題は、「その合計値が作れるかどうか」を動的計画法（DP）の要領でテーブルに記録しながら求めることで解けます。手順は以下の通りです。

• MAX := 1000（扱う合計値の上限）
• table := サイズ MAX の配列を用意し、すべて 0 で初期化する
• 関数 util() を定義する。引数は nums
• table[0] := 1（合計 0 は常に作れる）
• リスト nums をソートする
• i を 0 から nums のサイズ - 1 まで繰り返す：
  • val := nums[i]
  • もし table[val] が 0 以外なら、次の反復へ進む（重複処理の回避）
  • j を 0 から MAX - val - 1 まで繰り返す：
    • もし table[j] が 0 以外なら、table[j + val] := 1 とする
• メイン側では次を行う：
  • util(nums) を呼び出す
  • もし table[sum] が 0 以外なら True を返す
• それ以外の場合は False を返す

アルゴリズムのポイント

table[i] には「合計 i が作れるかどうか」を 0 / 1 で記録します。初期状態では table[0] = 1（何も選ばなければ合計は 0）だけが立っています。各要素 val について、すでに到達可能な位置 j から j + val へフラグを伝播させることで、同じ要素を何度使ってもよいタイプの到達可能性判定を実現しています。また、ある要素について table[val] がすでに 1 の場合は、その要素による更新は完了しているためスキップすることで、無駄な計算を省いています。全体の計算量はおおよそ O(要素数 × MAX) です。

理解を深めるために、以下の実装例を見てみましょう。

実装例

MAX = 1000
table = [0] * MAX

def util(nums):
    table[0] = 1
    nums.sort()
    for i in range(len(nums)):
        val = nums[i]
        if table[val]:
            continue
        for j in range(MAX - val):
            if table[j]:
                table[j + val] = 1

def solve(nums, sum):
    util(nums)
    if table[sum]:
        return True
    return False

nums = [2, 3, 5]
sum = 28
print(solve(nums, sum))

入力

[2, 3, 5], 28

出力

True

まとめ

このように、DPテーブルを使って到達可能な合計値を順にマークしていくことで、要素の再利用が許される場合の合計作成可否を効率よく判定できます。条件分岐やループの構造がシンプルなので、部分和問題の応用形としてぜひ覚えておきましょう。