Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में कॉम्बिनेशन सम


मान लीजिए हमारे पास उम्मीदवार संख्याओं का एक समूह है (सभी तत्व अद्वितीय हैं) और एक लक्ष्य संख्या। हमें उम्मीदवारों में उन सभी अद्वितीय संयोजनों को ढूंढना है जहां उम्मीदवार संख्याओं का योग दिए गए लक्ष्य के बराबर हो। वही संख्या उम्मीदवारों से असीमित बार चुनी जा सकती है। इसलिए यदि तत्व [2,3,6,7] हैं और लक्ष्य मान 7 है, तो संभावित आउटपुट [[7], [2,2,3]] होगा।

चरण देखें -

  • हम इसे पुनरावर्ती तरीके से हल करेंगे। पुनरावर्ती फ़ंक्शन का नाम solve() है। यह परिणामों को संग्रहीत करने के लिए एक सरणी, रिकॉर्ड रखने के लिए एक मैप, लक्ष्य मान और विशिष्ट तत्वों की एक सूची लेता है। प्रारंभ में res सरणी और मैप खाली होते हैं। solve विधि निम्नानुसार काम करेगी -

  • यदि लक्ष्य 0 है, तो
    • temp := सूची में मौजूद तत्वों की एक सूची
    • temp1 := temp, फिर temp को सॉर्ट करें
    • यदि temp मैप में नहीं है, तो temp को मैप में डालें और मान 1 सेट करें, temp को res में डालें
    • वापस लौटें
    • यदि temp < 0, तो वापस लौटें
    • x के लिए i से तत्व सूची की लंबाई तक की रेंज में
      • elements[x] को current में डालें
      • solve(elements, target - elements[x], res, map, i, current)
      • current सूची से इंडेक्स (current की लंबाई - 1) से तत्व हटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution(object):    def combinationSum(self, candidates, target):       result = []       unique={}       candidates = list(set(candidates))       self.solve(candidates,target,result,unique)       return result    def solve(self,candidates,target,result,unique,i = 0,current=[]):       if target == 0:          temp = [i for i in current]          temp1 = temp          temp.sort()          temp = tuple(temp)          if temp not in unique:             unique[temp] = 1             result.append(temp1)          return       if target <0:          return       for x in range(i,len(candidates)):          current.append(candidates[x])          self.solve(candidates,target-candidates[x],result,unique,i,current)          current.pop(len(current)-1) ob1 = Solution() print(ob1.combinationSum([2,3,6,7,8],10))

इनपुट

[2,3,6,7,8] 10

आउटपुट

[[2, 8], [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [3, 7]]

  1. पायथन में पथ योग पायथन में पथ योग

    मान लीजिए हमारे पास एक ट्री और एक योग है। हमें एक ऐसा पथ ढूंढना है जिससे यदि हम उस पथ का अनुसरण करें, तो हमें वह योग मिलेगा जो दिए गए योग से मेल खाता हो। मान लीजिए ट्री [0,-3,9,-10, null,5] जैसा है और योग 14 है, तो एक पथ 0 → 9 → 5 है। हल करने के चरण यदि रूट null है, तो False वापस करें यदि बायां औ

  1. - पायथन में टू सम

    मान लीजिए हमारे पास पूर्णांकों की एक सरणी है। हमें दो पूर्णांकों के सूचकांक वापस करने हैं, जैसे कि यदि हम उन्हें जोड़ते हैं, तो हम एक विशिष्ट लक्ष्य तक पहुंचेंगे जो भी दिया गया है। यहां हम एक मान्यता लेंगे, कि सरणी में हमेशा एक अद्वितीय समाधान होगा, इसलिए एक ही लक्ष्य के लिए दो सेट सूचकांक नहीं हों

  1. - पायथन में पर्म्यूटेशन और कॉम्बिनेशन

    पायथन का itertools मॉड्यूल पर्म्यूटेशन और कॉम्बिनेशन जेनरेट करने के लिए कुशल फंक्शन्स प्रदान करता है। इंस्टॉलेशन/इम्पोर्ट from itertools import permutations, combinations, combinations_with_replacement पर्म्यूटेशन (क्रम महत्वपूर्ण) क्रम में व्यवस्था: nPr = n! / (n-r)! उदाहरण 1: पूर्ण पर्म्यूटेशन