पायथन में सिक्कों और मात्राओं से अलग सिक्का योग की संख्या ढूंढने का प्रोग्राम

मान लीजिए हमारे पास coins नामक मानों की एक सूची है और उसी लंबाई की quantities नामक एक अन्य सूची है। iवें सिक्के का मान coins[i] है और हमारे पास वर्तमान में quantities[i] संख्या में iवां सिक्का है। हमें इन सिक्कों के गैर-खाली समूह का उपयोग करके प्राप्त होने वाले अलग सिक्का योग मानों की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट coins = [1, 2, 5] quantities = [1, 2, 1] है, तो आउटपुट 10 होगा, क्योंकि हमारे पास निम्न अलग सिक्का योग हो सकते हैं [1] = 1, [2] = 2, [1,2] = 3, [2,2] = 4, [5] = 5,[1,5] = 6, [2,5] = 7, [1,2,5] = 8, [2,2,5] = 9, [1,2,2,5] = 10।

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

एक फ़ंक्शन rec() परिभाषित करें। यह i, res लेगा

if i is same as size of coins , then    return for k in range 0 to quantities[i] + 1, do    cur := res + k * coins[i]    insert cur into fres    rec(i + 1, cur) मुख्य विधि से, निम्न करें: fres := एक नया सेट rec(0, 0) return size of fres - 1

उदाहरण

class Solution:    def solve(self, coins, quantities):       def rec(i, res):          if i == len(coins):             return          for k in range(0, quantities[i] + 1):             cur = res + k * coins[i]             fres.add(cur)             rec(i + 1, cur)       fres = set()       rec(0, 0)       return len(fres) - 1 ob = Solution() coins = [1, 2, 5] quantities = [1, 2, 1] print(ob.solve(coins, quantities))

इनपुट

[1, 2, 5], [1, 2, 1]

आउटपुट

10