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

Arnab Chakraborty

更新於: 2020-10-21

756 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習