Pythonで2つのパーティションのグループを同じ合計で作成できるかどうかを確認するプログラムはありますか？

numsと呼ばれる数値のリストがあるとすると、両方のグループの要素の合計が同じである2つのグループにnumsを分割できるかどうかを確認する必要があります。

したがって、入力がnums =[2、3、6、5]のような場合、[2、6]や[3、5]のようなグループを作成できるため、出力はTrueになります。

これを解決するために、次の手順に従います

• total：=numsのすべての要素の合計

• 合計が奇数の場合、

  • Falseを返す

• 半整数：=合計の整数部分/ 2

• dp：=サイズの半分+1のリストとfalseで埋める

• dp [0]：=true

• numsのnumごとに、実行します

  • iの範囲が半分から0の場合、1ずつ減らします。

    • i> =numの場合、

      • dp [i]：=dp[i]または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