পাইথনে কম্বিনেশন সম

मान लीजिए हमारे पास उम्मीदवार संख्याओं का एक समूह है (सभी तत्व अद्वितीय हैं) और एक लक्ष्य संख्या। हमें उम्मीदवारों में सभी अद्वितीय संयोजन ढूंढने हैं जहां उम्मीदवार संख्याओं का योग दिए गए लक्ष्य के बराबर हो। उम्मीदवारों से एक ही संख्या को असीमित बार चुना जा सकता है। इसलिए यदि तत्व [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]]