Pythonの特定の要素セットから特定の合計を取得できるかどうかを確認します

numsという配列と別の値の合計があるとします。 numsに存在する要素を追加して合計を取得できるかどうかを確認する必要があります。単一の要素を複数回選択する場合があります。

したがって、入力がnums =[2、3、5] sum =28のような場合、5 + 5 + 5 + 5 + 3 + 3 + 2

これを解決するには、次の手順に従います-

• MAX：=1000
• table：=0のサイズMAX広告塗りつぶしの配列
• 関数util（）を定義します。これには数がかかります
• table [0]：=1
• リスト番号を並べ替える
• 範囲0からnums-1のサイズのiの場合、do
  • val：=nums [i]
  • table [val]がゼロ以外の場合、
    • 次の反復に進む
  • 0〜MAXの範囲のjの場合-val-1、do
    • 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