Python में योग 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
• i के लिए 0 से nums के आकार - 1 तक रेंज में, करें
  • j के लिए k से 0 तक रेंज में, 1 से घटाते हुए, करें
    • यदि 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

आउटपुट

3