Pythonでリストを合計が等しくAの全要素がBより小さい2つのグループに分割できるか判定する方法

問題概要

数値のリスト nums が与えられたとき、このリストを2つのグループ A と B に分割できるかどうかを判定するプログラムを作成します。分割には以下の2つの条件を満たす必要があります。

• グループ A の合計とグループ B の合計が等しいこと
• グループ A 内のすべての数値が、グループ B 内のどの数値よりも厳密に小さいこと

例えば、nums = [3, 4, 5, 12] という入力の場合、出力は True になります。A = [3, 4, 5]、B = [12] とすれば、両方の合計が12となり、すべての条件を満たすからです。

解決アプローチ

この問題は、リストをソートして先頭から累積和を確認していくことで効率的に解けます。手順は以下の通りです。

1. リスト nums をソートする
2. 全要素の合計 total を求める
3. 累積和 s を 0、インデックス i を 0 で初期化する
4. i がリストの長さ未満である間、次を繰り返す:
   • n := nums[i] とする
   • i が範囲内かつ nums[i] == n の間、s に nums[i] を加算し i を進める(同じ値の要素をまとめて処理)
   • s == total - s であれば True を返す
5. ループ完了後は False を返す

ここでのポイントは、ソート済みリストに対して同じ値ごとにまとめて累積和を取る点です。これにより、A と B の境界が同一の値をまたぐことがなくなり、「A の最大値 < B の最小値」という条件が自動的に保証されます。

実装例

class Solution:
   def solve(self, nums):
      nums.sort()
      total = sum(nums)
      s = 0
      i = 0
      while i < len(nums):
         n = nums[i]
         while i < len(nums) and nums[i] == n:
            s += nums[i]
            i += 1
         if s == total - s:
            return True
      return False
ob = Solution()
nums = [3, 4, 5, 12]
print(ob.solve(nums))

入力

[3, 4, 5, 12]

出力

True

計算量の目安

ソートに O(n log n)、その後の線形走査に O(n) を要するため、全体の時間計算量は O(n log n) となります。ソートをインプレースで行えば、追加の空間計算量は O(1) で抑えられます。