समस्या
प्रत्येक दिए गए सिक्का मूल्य का कोई भी संख्या में उपयोग करके राशि को ठीक-ठीक बनाएं। संयोजनों की गिनती करें, क्रम की नहीं: यदि दो व्यवस्थाओं में प्रत्येक सिक्के की संख्या समान है, तो वे एक ही तरीका मानी जाएंगी। सभी सिक्का मूल्य अलग और धनात्मक हैं।
coin_sums(amount, coins) को लागू करें।
इनपुट
amount: वह कुल राशि जिसे बनाना है।
coins: उपलब्ध अलग-अलग सिक्का मूल्य।
आउटपुट
संयोजनों (क्रम रहित) की संख्या लौटाएं।
सीमाएँ
0 ≤ amount ≤ 200। 0 से 10 तक अलग-अलग सिक्का मूल्य हो सकते हैं, प्रत्येक 1 से 200 के बीच। सभी गिनतियां signed 64-bit में समा जाती हैं। राशि 0 के लिए एक ही तरीका है: कोई सिक्का न चुनें।
उदाहरण
इनपुट:
coins = [1, 2]
amount = 4
अपेक्षित आउटपुट:
expected = 3इनपुट:
std::vector<long long> coins = {1, 2};
long long amount = 4;
अपेक्षित आउटपुट:
long long expected = 3;इनपुट:
long[] coins = new long[] {1, 2};
long amount = 4;
अपेक्षित आउटपुट:
long expected = 3;व्याख्या
संयोजन हैं: चार 1 वाले, दो 1 और एक 2 वाला, तथा दो 2 वाले।
इनपुट:
coins = [2]
amount = 3
अपेक्षित आउटपुट:
expected = 0इनपुट:
std::vector<long long> coins = {2};
long long amount = 3;
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long[] coins = new long[] {2};
long amount = 3;
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
2 मूल्य वाले सिक्कों का कोई भी योग हमेशा सम होगा, इसलिए 3 बनाना असंभव है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Coins का order matter नहीं करता, इसलिए combinations को denomination के हिसाब से count करो, permutation के हिसाब से नहीं।
संकेत 2
हर amount के लिए ways को incrementally build करो, ताकि हर coin सभी reachable totals में योगदान दे सके।
संकेत 3
Amount zero को ध्यान से handle करो, क्योंकि उसका हमेशा एक valid way होता है: कोई coin नहीं चुनना।
अपेक्षित जटिलता
समय O(amount × number_of_coins), अतिरिक्त स्थान O(amount)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।