पायथन में k तक योग देने वाले विशिष्ट संयोजनों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक विशिष्ट संख्याओं की एक सूची और एक संख्या k है, हमें उन विशिष्ट संयोजनों की संख्या ढूंढनी है जिनका योग k तक है। संयोजन बनाते समय आप संख्याओं का पुनः उपयोग कर सकते हैं।

उदाहरण के लिए, यदि इनपुट nums = [2, 4, 5] और k = 4 है, तो आउटपुट 2 होगा, क्योंकि हम [2, 2] और [4] जैसे दो ऐसे समूह बना सकते हैं।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• table := आकार k+1 की सूची, 0 से भरी हुई
• table[0] := 1
• प्रत्येक num के लिए nums में:
  • i को num से k तक:
    • table[i] := table[i] + table[i - num]
• table[k] लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, nums, k):
        table = [1] + [0] * k
        for num in nums:
            for i in range(num, k + 1):
                table[i] += table[i - num]
        return table[k]

ob = Solution()
nums = [2, 4, 5]
k = 4
print(ob.solve(nums, k))

इनपुट

[2, 4, 5], 4

आउटपुट

2