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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告