파이썬에서 합이 k인 부분 집합을 계산하는 프로그램

nums라고 하는 숫자 목록과 다른 값 k가 있다고 가정하면 목록에서 k가 되는 부분 집합의 수를 찾아야 합니다. 답이 매우 크면 이것을 10^9 + 7

따라서 입력이 nums =[2, 3, 4, 5, 7] k =7과 같으면 하위 집합 [2,5],[3,4] 및 [ 7].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• dp :=크기 목록(k + 1) 및 0으로 채우기
• dp[0] :=1
• m :=10^9 + 7
• 0부터 숫자 - 1까지의 범위에 있는 i에 대해
  • k 범위에서 0까지의 j에 대해 1만큼 감소, do
    • 숫자[i] <=j이면
      • dp[j] :=dp[j] + dp[j - 숫자[i]]
      • dp[j] :=dp[j] 모드 m

• dp[k] 모드 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