用 Python 编写程序检查是否可以将两个分区分成总和相等的组?

pythonserver side programmingprogramming更新于 2026/2/16 17:48:17

假设我们有一个名为 nums 的数字列表，我们必须检查是否可以将 nums 分成两组，其中两组中元素的总和相同。

因此，如果输入为 nums = [2, 3, 6, 5]，则输出将为 True，因为我们可以创建如下组:[2, 6] 和 [3, 5]。

要解决这个问题，我们将遵循以下步骤

total := nums 中所有元素的总和
如果 total 为奇数，则
- 返回 False
half := total 的整数部分 / 2
dp := 大小为 half + 1 的列表并用 false 填充
dp[0] := true
对于 nums 中的每个数字，执行
- 对于范围为 half 到 0 的 i，减少 1，执行
  - 如果 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))