Combination Sum
मान लीजिए हमारे पास एक लक्ष्य मान
N है और कुछ पॉज़िटिव संख्याओं का एक ऐरे दिया गया है। हमारा काम है यह पता लगाना कि उन दी गई संख्याओं को जोड़कर N कैसे बनाया जा सकता है, यानी कुल कितने तरीक़े हैं।उदाहरण के लिए, यदि हमारे अनुमत मान
[1, 2, 3] हों और N की मान 4 हो, तो 1, 2, 3 को जोड़कर 4 प्राप्त करने के कुल 7 तरीक़े हैं:1, 2, 3 को जोड़कर 4 प्राप्त करने के 7 तरीके
- 1 + 1 + 1 + 1
- 1 + 1 + 2
- 1 + 2 + 1
- 2 + 1 + 1
- 1 + 3
- 3 + 1
- 2 + 2
यह एक क्लासिक डायनेमिक प्रोग्रामिंग समस्या है, जिसे इस तरह हल किया जा सकता है कि हम एक स्टेट बनाएँ
d[sum], जो यह दर्शाती है कि किसी भी sum को बनाने के कितने तरीक़े हैं, जब हमारे पास दी गई संख्याओं का सेट मौजूद हो:N = ...
nums = [...]
d = [0] * (N + 1) # d[i] = उन सभी कॉम्बिनेशंस की गिनती जो i का योग देती हैं
d[0] = 1 # 0 बनाने का 1 तरीक़ा है - कोई भी संख्या न लेना
for i in range(1, N + 1): # 1...N तक सभी संख्याओं को बनाने की कोशिश
for num in nums: # d[i] बनाए रखने के लिए nums की मदद से संभवता जाँचें
if i - num >= 0:
d[i] += d[i - num]
print(d[N])हमारी स्टेट
d[i] दर्शाती है कि हम i को nums की मदद से कितने तरीक़ों से बना सकते हैं। शुरू में हम सब कुछ 0 से इनिशलाइज़ करते हैं, सिवाय d[0] के, जिसे 1 सेट करते हैं क्योंकि 0 सिर्फ़ एक ही तरीक़े से बन सकता है – कोई संख्या न लेकर। इसके बाद, जब हम बाकी मानों पर जाते हैं, तो हर संख्या के लिए जाँचते हैं कि क्या उसे जोड़कर हम वह मान बना सकते हैं।उदाहरण के तौर पर, अगर
d[11] (11 बनाने के कुल तरीक़े) अभी 5 हैं, और d[8] (8 बनाने के कुल तरीक़े) 3 हैं, और यदि हमारे ऐरे nums में 3 मौजूद है, तो 11 बनाने के तरीक़ों की गिनती 5 से बढ़कर (3 को जोड़कर 8 से आने वाले) 3 और तरीक़े जोड़ लेगी।अब इसी एल्गोरिथ्म को ऊपर के उदाहरण पर लागू करके देखते हैं:
nums = [1, 2, 3] और N = 4
- शुरू में
d = [1, 0, 0, 0, 0]→ 0 बनाने का 1 तरीक़ा और बाकी सब 0
i = 1num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0
i = 2num = 1 ⇒ d[2] += d[1] ⇒ d = [1, 1, 1, 0, 0] num = 2 ⇒ d[2] += d[0] ⇒ d = [1, 1, 2, 0, 0] num = 3 ⇒ i - num < 0
i = 3num = 1 ⇒ d[3] += d[2] ⇒ d = [1, 1, 2, 2, 0] num = 2 ⇒ d[3] += d[1] ⇒ d = [1, 1, 2, 3, 0] num = 3 ⇒ d[3] += d[0] ⇒ d = [1, 1, 2, 4, 0]
i = 4num = 1 ⇒ d[4] += d[3] ⇒ d = [1, 1, 2, 4, 4] num = 2 ⇒ d[4] += d[2] ⇒ d = [1, 1, 2, 4, 6] num = 3 ⇒ d[4] += d[1] ⇒ d = [1, 1, 2, 4, 7]
print(d[4])→ 7 प्रदर्शित करता है
Challenge - Dice Combinations
कल्पना कीजिए कि आपके पास एक पासा (dice) है जो 1 से 6 तक कोई भी मान दे सकता है। आपका काम है यह पता लगाना कि अलग-अलग पासा फेंककर (और उनके मानों को जोड़कर) कोई संख्या
n कितने तरीक़ों से प्राप्त की जा सकती है।
इनपुट
इनपुट में एकल पूर्णांक
n (1 ≤ n ≤ ) दिया गया है।आउटपुट
आपको पासा फेंककर संख्या
n बनाने के सभी तरीक़ों की गिनती निकालनी है। क्योंकि उत्तर बहुत बड़ा हो सकता है, इसे से मोड लेना (modulo करना) होगा।Examples
Input | Output |
2 | 2 |
3 | 4 |
Explanation
- 2 → 1 + 1, 2
- 3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB