Python程式：檢查能否將列表分成兩個和相等的子集？

假設我們有一個名為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中的每個num，執行：

    • 對於從half到0的每個i（遞減），執行：

      • 如果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))

輸入

[2, 3, 6, 5]

輸出

True

更新於：2020年11月10日

205 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告