পাইথনে সাবসেটের সমষ্টি k হয় এমন সাবসেটের সংখ্যা গণনা করার প্রোগ্রাম

ধরি আমাদের একটি নাম্বার লিস্ট nums এবং আরেকটি মান k আছে। আমাদের লিস্টে এমন সাবসেটের সংখ্যা বের করতে হবে যাদের সমষ্টি k হয়। যদি উত্তর খুব বড় হয় তবে ১০^৯ + ৭ দিয়ে মড করুন।

তাই, ইনপুট যদি nums = [2, 3, 4, 5, 7], k = 7 হয়, তবে আউটপুট হবে ৩, কারণ সাবসেটগুলো হলো [2,5], [3,4] এবং [7]।

সমাধানের ধাপগুলো:

dp := (k+1) আকারের লিস্ট ০ দিয়ে ফিল করে
dp[0] := 1
m := 10^9 + 7
i = ০ থেকে len(nums)-1 পর্যন্ত, করুন
- j = k থেকে ০ পর্যন্ত ১ করে কমিয়ে, করুন
  - যদি nums[i] <= j, তবে
    - dp[j] := dp[j] + dp[j - nums[i]]
    - dp[j] := dp[j] mod m
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