检查是否可以使用给定的 Python 元素集合获得给定的总和

假设我们有一个名为 nums 的数组和另一个值 sum。我们必须检查是否可以通过添加 nums 中存在的元素来获得 sum，我们可以多次选择单个元素。

因此，如果输入类似于 nums = [2, 3, 5] sum = 28，则输出将为 True，因为我们可以使用 5 + 5 + 5 + 5 + 3 + 3 + 2 得到 28。

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

  • MAX := 1000
  • table := 一个大小为 MAX 的数组，并用 0 填充
  • 定义一个函数 util()。这将采用 nums
  • table[0] := 1
  • 对列表 nums 进行排序
  • 对于 i 的范围为 0 到 nums 的大小 - 1，执行：
    • val := nums[i]
    • 如果 table[val] 不为零，则
      • 进行下一次迭代
    • 对于 j 的范围为 0 到 MAX - val - 1，执行：
      • 如果 table[j] 不为零，则
        • table[j + val] := 1
  • 从主方法执行以下操作：
  • util(nums)
  • 如果 table[sum] 不为零，则
    • 返回 True
  • 返回 False

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

示例

 在线演示

MAX = 1000
table = [0] * MAX
def util(nums):
   table[0] = 1
   nums.sort()
   for i in range(len(nums)):
      val = nums[i]
      if table[val]:
         continue
      for j in range(MAX - val):
         if table[j]:
            table[j + val] = 1
def solve(nums, sum):
   util(nums)
   if table[sum]:
      return True
   return False
nums = [2, 3, 5]
sum = 28
print (solve(nums, sum))

输入

[2, 3, 5], 28

输出

True

更新于：2021年1月18日

421 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告