পাইথনে k পর্যন্ত যোগফলের উপসেট গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় nums এবং আরেকটি মান k, আমাদেরকে তালিকায় উপসেটের সংখ্যা খুঁজে বের করতে হবে যেগুলির যোগফল k পর্যন্ত। উত্তরটি খুব বড় হলে 10^9 + 7

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• dp :=আকারের একটি তালিকা (k + 1) এবং 0 দিয়ে পূরণ করুন
• dp[0] :=1
• m :=10^9 + 7
• আমি 0 থেকে সংখ্যার আকার - 1 এর মধ্যে, কর
  • j-এর জন্য k রেঞ্জ 0 থেকে কম, 1 কম করুন,
    করুন
    • যদি সংখ্যা[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

আউটপুট

3