Pythonでリストを合計が等しい2つのグループに分割できるか判定する方法

数値のリスト nums が与えられたとき、その要素を2つのグループに分割し、それぞれのグループに含まれる要素の合計が等しくなるようにできるかどうかを判定することを考えます。

例えば、入力が nums = [2, 3, 6, 5] の場合、[2, 6] と [3, 5] という2つのグループに分けることができるため、出力は True になります。

解決のアプローチ

この問題は、動的計画法（DP）を用いた「部分和問題」として解くことができます。ポイントは、まず全体の合計を求め、それが偶数であれば「合計の半分に等しい部分和が作れるか」を確認するだけだという点です。具体的には以下の手順で進めます。

• total := nums の全要素の合計を求める

• total が奇数の場合は False を返す（2つのグループで同じ合計にできないため）

• half := total ÷ 2 の整数部分

• dp := サイズ half + 1 のリストを用意し、すべて False で初期化する

• dp[0] := True とする（合計0は常に達成可能なため）

• nums の各要素 num に対して、i を half から 0 へ降順にループし、i ≥ num であれば dp[i] = dp[i] OR dp[i - num] と更新する

• 最後に dp[half] を返す

内側のループを降順に処理するのは重要なテクニックです。昇順に処理すると同じ要素を何度も使ってしまう可能性がありますが、降順にすることで各要素を一度しか使わないことを保証できます。

実装例

class Solution:
   def solve(self, nums):

      total = sum(nums)

      if total & 1:
         return False

      half = total // 2

      dp = [True] + [False] * half
      for num in nums:
         for i in range(half, 0, -1):
            if i >= num:
               dp[i] |= dp[i - num]

      return dp[half]

ob = Solution()
nums = [2, 3, 6, 5]
print(ob.solve(nums))

入力

[2, 3, 6, 5]

出力

True

このように、DPテーブルを活用することで、リストを合計の等しい2つのグループに分割できるかどうかを効率的に判定できます。計算量は O(n × half) となり、要素数や合計値がそれほど大きくない場合に実用的な手法です。