Python程序：将集合拆分为和相等的两组，其中第一组的元素小于第二组

假设我们有一个名为 nums 的数字列表，我们需要检查是否可以将列表分成两组 A 和 B，使得：A 的和与 B 的和相同。这里 A 中的每个数字都严格小于 B 中的每个数字。

因此，如果输入类似于 nums = [3, 4, 5, 12]，则输出将为 True，因为我们可以有 A = [3,4,5] 和 B = [12]，并且两者之和都为 12。

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

  • 对列表 nums 进行排序

  • total := nums 中所有元素的总和

  • s := 0，i := 0

  • 当 i < nums 的大小，执行以下操作：

    • n := nums[i]

    • 当 i < nums 的大小且 nums[i] 与 n 相同，执行以下操作：

      • s := s + nums[i]

      • i := i + 1

    • 如果 s 与 total - s 相同，则：

      • 返回 True

  • 返回 False

让我们看一下下面的实现，以便更好地理解：

示例

 在线演示

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

更新于: 2020-10-21

756 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告