पायथन में संयोजन योग

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

आइए चरणों को देखें -

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

• यदि लक्ष्य 0 है, तो
  • अस्थायी:=सूची में मौजूद तत्वों की सूची
  • temp1 :=temp, फिर temp को सॉर्ट करें
  • यदि अस्थायी मानचित्र में नहीं है, तो मानचित्र में अस्थायी डालें और मान 1 के रूप में सेट करें, अस्थायी को रेस में डालें
  • वापसी
  • अगर अस्थायी <0, तो वापस आएं
  • x के लिए श्रेणी I से तत्व सूची की लंबाई तक,
    • तत्वों को डालें[x] को करंट में डालें
    • समाधान (तत्व, लक्ष्य - तत्व [x], रेस, मानचित्र, i, वर्तमान)
    • सूचकांक से वर्तमान सूची से तत्व हटाएं (वर्तमान की लंबाई -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]]