檢查是否可以使用給定的 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

Arnab Chakraborty

更新於：2021年1月18日

421 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始