Pythonで合計kまでのサブセットをカウントするプログラム

numsと呼ばれる数値のリストと別の値kがあるとすると、リスト内で合計kになるサブセットの数を見つける必要があります。答えが非常に大きい場合は、これを10 ^ 9 + 7

したがって、入力がnums =[2、3、4、5、7] k =7のような場合、サブセット[2,5]、[3,4]、および[を選択できるため、出力は3になります。 7]。

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

• dp：=サイズ（k + 1）のリストで、0で埋めます
• dp [0]：=1
• m：=10 ^ 9 + 7
• 範囲0からnums-1のサイズのiの場合、do
  • kから0までの範囲のjの場合、1ずつ減らします。
    • nums [i] <=jの場合、
      • dp [j]：=dp [j] + dp [j --nums [i]]
      • dp [j]：=dp [j] mod m

• return dp [k] mod m

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, nums, k):
      dp = [0] * (k + 1)
      dp[0] = 1
      m = int(1e9 + 7)
      for i in range(len(nums)):
         for j in range(k, -1, -1):
            if nums[i] <= j:
               dp[j] += dp[j - nums[i]]
               dp[j] %= m
      return dp[k] % m

ob = Solution()
nums = [2, 3, 4, 5, 7]
k = 7
print(ob.solve(nums, k))

入力

[2, 3, 4, 5, 7], 7

出力

3