पायथन में k तक योग करने वाले सबसेट को गिनने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k है, हमें सूची में सबसेट की संख्या ज्ञात करनी है जो k तक है। अगर उत्तर बहुत बड़ा है तो इसे 10^9 + 7

इसलिए, यदि इनपुट संख्या =[2, 3, 4, 5, 7] k =7 की तरह है, तो आउटपुट 3 होगा, क्योंकि हम सबसेट [2,5], [3,4] और [ 7].

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• dp :=आकार की सूची (k + 1) और 0 से भरें
• dp[0] :=1
• म :=10^9 + 7
• i के लिए 0 से लेकर अंकों के आकार -1 तक के लिए
  • j के लिए k से 0 तक की श्रेणी में, 1 से घटाएं
    • यदि अंक[i] <=j, तो
      • dp[j] :=dp[j] + dp[j - nums[i]]
      • dp[j] :=dp[j] 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