दिलचस्प पोस्ट
पीडीएफ फाइल को HTML लिंक में डाउनलोड करने योग्य कैसे बनाऊं? एएसपी.एनटी वेब एपीआई में त्रुटियों की वापसी के लिए सर्वश्रेष्ठ अभ्यास एंड्रॉइड डाटाबेस (एसक्यूएलईटी) में सहेजे गए डेटा को कैसे देखें? JQuery के उपयोग से मैं webservice के लिए विंडोज प्रमाणीकरण कैसे पार करूं? स्थानीय एप्लिकेशन डेटा निर्देशिका के पथ को प्राप्त करने का क्रॉस-प्लेटफ़ॉर्म तरीका क्या है? मिलान कोष्ठक को संतुलित करने के लिए RegEx का उपयोग करना पूर्ण स्क्रीन जावा में जेफ्रेम आईफोन वेब ऐप – शरीर स्क्रॉलिंग रोकें जावा 8 सामान्य प्रकार अनुमान इस अधिभार क्यों उठाते हैं? उद्देश्य-सी ++ कितनी अच्छी तरह समर्थित है? एंड्रॉइड ऐप में डेटा को कैसे बचाया जाए त्रुटि: '..' में सदस्य '..' के लिए अनुरोध जो कि गैर-वर्ग प्रकार का है क्या मुझे एक Global.asax.cs फ़ाइल की ज़रूरत है अगर मैं एक ओविन स्टार्टअप सीसीएस क्लास का उपयोग कर रहा हूं और वहां सभी कॉन्फ़िगरेशन को स्थानांतरित कर रहा हूं? कैसे PHP में एक खाली सरणी में तत्वों को जोड़ने के लिए? प्रदर्शन परीक्षण के लिए सटीक समय माप

दिए गए योग तक पहुंचने के लिए सभी संभावित संयोजनों को ढूंढना

संख्याओं के दिए गए सेट से जोड़ के सभी संभावित संयोजनों का परीक्षण करने के बारे में आप कैसे जा सकते हैं ताकि वे किसी दिए गए अंतिम संख्या में जोड़ दें?

उदाहरण:

  • जोड़ने के लिए नंबरों का सेट: {1,5,22,15,0, …}
  • वांछित परिणाम: 12345

Solutions Collecting From Web of "दिए गए योग तक पहुंचने के लिए सभी संभावित संयोजनों को ढूंढना"

इस समस्या को उन सभी संभावित रकम के एक पुनरावर्ती संयोजन के साथ हल किया जा सकता है जो लक्ष्य तक पहुंचते हैं। पायथन में एल्गोरिथम यहाँ है:

def subset_sum(numbers, target, partial=[]): s = sum(partial) # check if the partial sum is equals to target if s == target: print "sum(%s)=%s" % (partial, target) if s >= target: return # if we reach the number why bother to continue for i in range(len(numbers)): n = numbers[i] remaining = numbers[i+1:] subset_sum(remaining, target, partial + [n]) if __name__ == "__main__": subset_sum([3,9,8,4,5,7,10],15) #Outputs: #sum([3, 8, 4])=15 #sum([3, 5, 7])=15 #sum([8, 7])=15 #sum([5, 10])=15 

इस प्रकार के एल्गोरिदम को निम्नलिखित स्टैंडफोर्ड एब्रेक प्रोग्रामिंग व्याख्यान में बहुत अच्छी तरह से समझाया गया है – यह वीडियो समझने के लिए बहुत ही अनुशंसित है कि रिकर्सन समाधान के क्रमपरिवर्तन कैसे उत्पन्न करता है।

संपादित करें

ऊपर एक जनरेटर समारोह के रूप में, इसे थोड़ा और अधिक उपयोगी बनाने के लिए से yield from वजह से अजगर 3.3+ की आवश्यकता है

 def subset_sum(numbers, target, partial=[], partial_sum=0): if partial_sum == target: yield partial if partial_sum >= target: return for i, n in enumerate(numbers): remaining = numbers[i + 1:] yield from subset_sum(remaining, target, partial + [n], partial_sum + n) 

यहां एक ही एल्गोरिथ्म का जावा संस्करण है:

 package tmp; import java.util.ArrayList; import java.util.Arrays; class SumSet { static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) { int s = 0; for (int x: partial) s += x; if (s == target) System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target); if (s >= target) return; for(int i=0;i<numbers.size();i++) { ArrayList<Integer> remaining = new ArrayList<Integer>(); int n = numbers.get(i); for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j)); ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial); partial_rec.add(n); sum_up_recursive(remaining,target,partial_rec); } } static void sum_up(ArrayList<Integer> numbers, int target) { sum_up_recursive(numbers,target,new ArrayList<Integer>()); } public static void main(String args[]) { Integer[] numbers = {3,9,8,4,5,7,10}; int target = 15; sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target); } } 

यह वास्तव में एक ही अनुमानी है मेरा जावा थोड़ा जंग खाए है, लेकिन मुझे लगता है कि समझने में आसान है।

जावा समाधान का सी # रूपांतरण: (जेरेमी टेम्प्सन द्वारा)

 public static void Main(string[] args) { List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 }; int target = 15; sum_up(numbers, target); } private static void sum_up(List<int> numbers, int target) { sum_up_recursive(numbers, target, new List<int>()); } private static void sum_up_recursive(List<int> numbers, int target, List<int> partial) { int s = 0; foreach (int x in partial) s += x; if (s == target) Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target); if (s >= target) return; for (int i = 0; i < numbers.Count; i++) { List<int> remaining = new List<int>(); int n = numbers[i]; for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]); List<int> partial_rec = new List<int>(partial); partial_rec.Add(n); sum_up_recursive(remaining, target, partial_rec); } } 

रूबी समाधान: (@मेमेलिन द्वारा)

 def subset_sum(numbers, target, partial=[]) s = partial.inject 0, :+ # check if the partial sum is equals to target puts "sum(#{partial})=#{target}" if s == target return if s >= target # if we reach the number why bother to continue (0..(numbers.length - 1)).each do |i| n = numbers[i] remaining = numbers.drop(i+1) subset_sum(remaining, target, partial + [n]) end end subset_sum([3,9,8,4,5,7,10],15) 

संपादित करें: जटिलता चर्चा

जैसा कि दूसरों का उल्लेख है यह एनपी-हार्ड समस्या है यह घातीय समय में हल किया जा सकता है ओ (2 ^ एन), उदाहरण के लिए n = 10 के लिए 1024 संभव समाधान होंगे। यदि आप तक पहुंचने का प्रयास कर रहे लक्ष्य कम सीमा में हैं तो यह एल्गोरिथ्म काम करता है। उदाहरण के लिए:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) 1024 शाखाएं उत्पन्न करता है क्योंकि लक्ष्य संभावित समाधानों को कभी भी फिल्टर नहीं करता है।

दूसरी तरफ subset_sum([1,2,3,4,5,6,7,8,9,10],10) केवल 175 शाखाएं उत्पन्न करती है, क्योंकि 10 तक पहुंचने का लक्ष्य कई संयोजनों को फ़िल्टर कर देता है।

यदि N और Target बड़ी संख्या हैं तो समाधान के अनुमानित संस्करण में जाना चाहिए।

हास्केल में :

 filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..] 

और जे :

 (]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ... 

जैसा कि आप देख सकते हैं, दोनों एक ही दृष्टिकोण लेते हैं और समस्या को दो हिस्सों में विभाजित करते हैं: प्रत्येक सेट को पावर सेट उत्पन्न करते हैं, और लक्ष्य के प्रत्येक सदस्य की राशि को जांचें।

अन्य समाधान हैं लेकिन यह सबसे सरल है।

क्या आपको किसी एक के साथ मदद की ज़रूरत है, या एक अलग दृष्टिकोण ढूंढने की आवश्यकता है?

इस समस्या का समाधान इंटरनेट पर एक लाख बार दिया गया है। समस्या को सिक्का बदलती समस्या कहा जाता हैhttp://rosettacode.org/wiki/Count_the_coins और http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (या Google सिक्का परिवर्तन पर) के गणितीय मॉडल पर समाधान प्राप्त कर सकते हैं समस्या )

वैसे, Tsagadai द्वारा Scala समाधान, दिलचस्प है यह उदाहरण या तो 1 या 0 का उत्पादन करता है। एक साइड इफेक्ट के रूप में, यह सभी संभव समाधान कंसोल पर सूचीबद्ध करता है। यह समाधान प्रदर्शित करता है, लेकिन इसे किसी भी तरह से प्रयोग करने में विफल रहता है।

समाधान की संख्या (सूचियों की सूची की लंबाई), "सर्वश्रेष्ठ" समाधान (सबसे कम सूची) या सभी को प्राप्त करने के लिए कोड को List[List[Int]] रूप में यथासंभव उपयोगी होना चाहिए संभावित समाधान

यहाँ एक उदाहरण है। यह बहुत ही अक्षम है, लेकिन यह समझना आसान है।

 object Sum extends App { def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = { def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = { (x._1 + y._1, x._2 ::: y._2) } def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = { if (numbers.isEmpty || total < 0) { (0, resultAcc) } else if (total == 0) { (1, sumAcc :: resultAcc) } else { add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers)) } } sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2 } println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n") } 

चलाते समय, यह प्रदर्शित करता है:

 List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2) List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2) List(1, 1, 1, 2, 2, 2, 2, 2, 2) List(1, 2, 2, 2, 2, 2, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5) List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5) List(1, 1, 1, 1, 1, 1, 2, 2, 5) List(1, 1, 1, 1, 2, 2, 2, 5) List(1, 1, 2, 2, 2, 2, 5) List(2, 2, 2, 2, 2, 5) List(1, 1, 1, 1, 1, 5, 5) List(1, 1, 1, 2, 5, 5) List(1, 2, 2, 5, 5) List(5, 5, 5) List(1, 1, 1, 1, 1, 10) List(1, 1, 1, 2, 10) List(1, 2, 2, 10) List(5, 10) 

sumCombinations() फ़ंक्शन का उपयोग स्वयं ही किया जा सकता है, और "सबसे अच्छा" समाधान (सबसे कम सूची), या समाधान की संख्या (सूचियों की संख्या) को प्रदर्शित करने के लिए परिणाम का विश्लेषण किया जा सकता है।

ध्यान दें कि यहां तक ​​कि यह भी पूरी तरह से संतुष्ट नहीं हो सकता है। ऐसा हो सकता है कि समाधान में प्रत्येक सूची का क्रम महत्वपूर्ण हो। ऐसे मामले में, प्रत्येक सूची को कई बार डुप्लिकेट करना होगा क्योंकि उसके तत्वों का संयोजन होता है। या हम केवल उन संयोजनों में दिलचस्पी ले सकते हैं जो अलग-अलग हैं

उदाहरण के लिए, हम विचार कर सकते हैं कि List(5, 10) को दो संयोजन देना चाहिए: List(5, 10) और List(10, 5)List(5, 5, 5) यह आवश्यकताओं के आधार पर तीन संयोजन या केवल एक ही दे सकता है पूर्णांकियों के लिए, तीन क्रमांतर समकक्ष हैं, लेकिन अगर हम सिक्के के साथ काम कर रहे हैं, जैसे "सिक्का बदलती समस्या", वे नहीं हैं।

इसके अलावा आवश्यकताओं में नहीं बताया गया है कि क्या प्रत्येक नंबर (या सिक्का) का इस्तेमाल केवल एक बार या कई बार किया जा सकता है। हम (और हमें चाहिए!) प्रत्येक संख्या की घटनाओं की सूचियों की सूची में समस्या को सामान्य बना सकते हैं यह वास्तविक जीवन में "सिक्कों के एक सेट के साथ एक निश्चित राशि बनाने के संभावित तरीके हैं (और सिक्का मूल्यों का कोई सेट नहीं है)" में अनुवाद करता है। मूल समस्या यह सिर्फ एक विशेष मामले है, जहां हमारे प्रत्येक सिक्का के रूप में कई घटनाएं होती हैं, जैसे प्रत्येक एक सिक्का मूल्य के साथ कुल राशि बनाने के लिए।

एक जावास्क्रिप्ट संस्करण:

 function subsetSum(numbers, target, partial) { var s, n, remaining; partial = partial || []; // sum partial s = partial.reduce(function (a, b) { return a + b; }, 0); // check if the partial sum is equals to target if (s === target) { console.log("%s=%s", partial.join("+"), target) } if (s >= target) { return; // if we reach the number why bother to continue } for (var i = 0; i < numbers.length; i++) { n = numbers[i]; remaining = numbers.slice(i + 1); subsetSum(remaining, target, partial.concat([n])); } } subsetSum([3,9,8,4,5,7,10],15); // output: // 3+8+4=15 // 3+5+7=15 // 8+7=15 // 5+10=15 

@ एमएसएलवाडोरस कोड का सी # संस्करण

 void Main() { int[] numbers = {3,9,8,4,5,7,10}; int target = 15; sum_up(new List<int>(numbers.ToList()),target); } static void sum_up_recursive(List<int> numbers, int target, List<int> part) { int s = 0; foreach (int x in part) { s += x; } if (s == target) { Console.WriteLine("sum(" + string.Join(",", part.Select(n => n.ToString()).ToArray()) + ")=" + target); } if (s >= target) { return; } for (int i = 0;i < numbers.Count;i++) { var remaining = new List<int>(); int n = numbers[i]; for (int j = i + 1; j < numbers.Count;j++) { remaining.Add(numbers[j]); } var part_rec = new List<int>(part); part_rec.Add(n); sum_up_recursive(remaining,target,part_rec); } } static void sum_up(List<int> numbers, int target) { sum_up_recursive(numbers,target,new List<int>()); } 

उसी एल्गोरिथम का सी ++ संस्करण

 #include <iostream> #include <list> void subset_sum_recursive(std::list<int> numbers, int target, std::list<int> partial) { int s = 0; for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++) { s += *cit; } if(s == target) { std::cout << "sum(["; for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++) { std::cout << *cit << ","; } std::cout << "])=" << target << std::endl; } if(s >= target) return; int n; for (std::list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++) { n = *ai; std::list<int> remaining; for(std::list<int>::const_iterator aj = ai; aj != numbers.end(); aj++) { if(aj == ai)continue; remaining.push_back(*aj); } std::list<int> partial_rec=partial; partial_rec.push_back(n); subset_sum_recursive(remaining,target,partial_rec); } } void subset_sum(std::list<int> numbers,int target) { subset_sum_recursive(numbers,target,std::list<int>()); } int main() { std::list<int> a; a.push_back (3); a.push_back (9); a.push_back (8); a.push_back (4); a.push_back (5); a.push_back (7); a.push_back (10); int n = 15; //std::cin >> n; subset_sum(a, n); return 0; } 

मैंने सोचा कि मैं इस सवाल का जवाब इस्तेमाल करूँगा लेकिन मैं नहीं कर सकता, इसलिए मेरा जवाब है। यह संरचना और इंटरप्रिटेशन ऑफ कंप्यूटर प्रोग्राम में एक उत्तर के एक संशोधित संस्करण का उपयोग कर रहा है मुझे लगता है कि यह एक बेहतर पुनर्रचनात्मक समाधान है और शुद्धतावादियों को और अधिक कृपया चाहिए।

मेरा जवाब स्कला में है (और अगर मेरे स्काला बेकार है, तो मैं इसे सीखना शुरू कर दिया है)। FindSumCombination पागलपन dupes रोकने के लिए recursion के लिए मूल सूची को सॉर्ट और अद्वितीय है।

 def findSumCombinations(target: Int, numbers: List[Int]): Int = { cc(target, numbers.distinct.sortWith(_ < _), List()) } def cc(target: Int, numbers: List[Int], solution: List[Int]): Int = { if (target == 0) {println(solution); 1 } else if (target < 0 || numbers.length == 0) 0 else cc(target, numbers.tail, solution) + cc(target - numbers.head, numbers, numbers.head :: solution) } 

इसके प्रयेाग के लिए:

  > findSumCombinations(12345, List(1,5,22,15,0,..)) * Prints a whole heap of lists that will sum to the target * 
 Thank you.. ephemient 

मैंने अजगर से पीएचपी के ऊपर तर्क को बदल दिया है ..

 <?php $data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5)); $maxsum = 25; print_r(bestsum($data,$maxsum)); //function call function bestsum($data,$maxsum) { $res = array_fill(0, $maxsum + 1, '0'); $res[0] = array(); //base case foreach($data as $group) { $new_res = $res; //copy res foreach($group as $ele) { for($i=0;$i<($maxsum-$ele+1);$i++) { if($res[$i] != 0) { $ele_index = $i+$ele; $new_res[$ele_index] = $res[$i]; $new_res[$ele_index][] = $ele; } } } $res = $new_res; } for($i=$maxsum;$i>0;$i--) { if($res[$i]!=0) { return $res[$i]; break; } } return array(); } ?> 

Excel का उपयोग करके संयोजनों को खोजने के लिए – (इसकी काफी आसान)। (आप कंप्यूटर बहुत धीमा नहीं होना चाहिए)

  1. इस साइट पर जाएं
  2. "योग के लिए लक्ष्य" पृष्ठ पर जाएं
  3. डाउनलोड करने के लिए "Sum to Target" Excel फ़ाइल डाउनलोड करें

    वेबसाइट पृष्ठ पर दिए गए निर्देशों का पालन करें।

उम्मीद है की यह मदद करेगा।

यहां एक जावा संस्करण है जो छोटे एन और बहुत बड़ा लक्ष्य योग के लिए अनुकूल है, जब जटिलता O(t*N) (गतिशील समाधान) घातीय एल्गोरिथम से अधिक है मेरा संस्करण क्लासिक अनुभवहीन O(n*2^n) से O(2^(n/2)) की जटिलता को कम करने के लिए थोड़ा सा स्थानांतरण के बीच, मध्य आक्रमण में एक बैठक का उपयोग करता है।

यदि आप इसे 32 और 64 तत्वों के बीच सेट के लिए उपयोग करना चाहते हैं, तो आपको उस अंतर को बदलना चाहिए जो वर्तमान चरण को वर्तमान चरण में फ़ंक्शन में दर्शाता है, हालांकि प्रदर्शन निश्चित रूप से सेट आकार बढ़ने के कारण स्पष्ट रूप से घट जाएगा। यदि आप तत्वों के अजीब संख्या के साथ एक सेट के लिए इसका उपयोग करना चाहते हैं, तो आपको इसे 0 में जोड़कर जोड़कर जोड़ना चाहिए।

 import java.util.ArrayList; import java.util.List; public class SubsetSumMiddleAttack { static final int target = 100000000; static final int[] set = new int[]{ ... }; static List<Subset> evens = new ArrayList<>(); static List<Subset> odds = new ArrayList<>(); static int[][] split(int[] superSet) { int[][] ret = new int[2][superSet.length / 2]; for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i]; return ret; } static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) { accumulator.add(new Subset(subset, sum)); if (counter != superSet.length) { step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1); step(superSet, accumulator, subset, sum, counter + 1); } } static void printSubset(Subset e, Subset o) { String ret = ""; for (int i = 0; i < 32; i++) { if (i % 2 == 0) { if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i]; } else { if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i]; } } if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum); System.out.println(ret); } public static void main(String[] args) { int[][] superSets = split(set); step(superSets[0], evens, 0,0,0); step(superSets[1], odds, 0,0,0); for (Subset e : evens) { for (Subset o : odds) { if (e.sum + o.sum == target) printSubset(e, o); } } } } class Subset { int subset; int sum; Subset(int subset, int sum) { this.subset = subset; this.sum = sum; } } 

यह सिक्का परिवर्तन की समस्या के समान है

 public class CoinCount { public static void main(String[] args) { int[] coins={1,4,6,2,3,5}; int count=0; for (int i=0;i<coins.length;i++) { count=count+Count(9,coins,i,0); } System.out.println(count); } public static int Count(int Sum,int[] coins,int index,int curSum) { int count=0; if (index>=coins.length) return 0; int sumNow=curSum+coins[index]; if (sumNow>Sum) return 0; if (sumNow==Sum) return 1; for (int i= index+1;i<coins.length;i++) count+=Count(Sum,coins,i,sumNow); return count; } } 

बहुत अच्छे एल्गोरिथ्म का इस्तेमाल करते हुए मैंने सी + + युगल में एक साल पहले लिखा था।

यदि आप प्रिंट 1 सेट करते हैं तो यह सभी संयोजन मुद्रित करेगा (लेकिन यह कुशल पद्धति का उपयोग नहीं किया जाएगा)।

इसकी इतनी कुशलता है कि यह 10 एमएमएस से कम 10 ^ 14 संयोजनों की गणना करता है।

 #include <stdio.h> #include <stdlib.h> //#include "CTime.h" #define SUM 300 #define MAXNUMsSIZE 30 #define PRINT 0 long long CountAddToSum(int,int[],int,const int[],int); void printr(const int[], int); long long table1[SUM][MAXNUMsSIZE]; int main() { int Nums[]={3,4,5,6,7,9,13,11,12,13,22,35,17,14,18,23,33,54}; int sum=SUM; int size=sizeof(Nums)/sizeof(int); int i,j,a[]={0}; long long N=0; //CTime timer1; for(i=0;i<SUM;++i) for(j=0;j<MAXNUMsSIZE;++j) table1[i][j]=-1; N = CountAddToSum(sum,Nums,size,a,0); //algorithm //timer1.Get_Passd(); //printf("\nN=%lld time=%.1f ms\n", N,timer1.Get_Passd()); printf("\nN=%lld \n", N); getchar(); return 1; } long long CountAddToSum(int s, int arr[],int arrsize, const int r[],int rsize) { static int totalmem=0, maxmem=0; int i,*rnew; long long result1=0,result2=0; if(s<0) return 0; if (table1[s][arrsize]>0 && PRINT==0) return table1[s][arrsize]; if(s==0) { if(PRINT) printr(r, rsize); return 1; } if(arrsize==0) return 0; //else rnew=(int*)malloc((rsize+1)*sizeof(int)); for(i=0;i<rsize;++i) rnew[i]=r[i]; rnew[rsize]=arr[arrsize-1]; result1 = CountAddToSum(s,arr,arrsize-1,rnew,rsize); result2 = CountAddToSum(s-arr[arrsize-1],arr,arrsize,rnew,rsize+1); table1[s][arrsize]=result1+result2; free(rnew); return result1+result2; } void printr(const int r[], int rsize) { int lastr=r[0],count=0,i; for(i=0; i<rsize;++i) { if(r[i]==lastr) count++; else { printf(" %d*%d ",count,lastr); lastr=r[i]; count=1; } } if(r[i-1]==lastr) printf(" %d*%d ",count,lastr); printf("\n"); } 

एक और अजगर समाधान itertools.combinations मॉड्यूल का उपयोग निम्नानुसार होगा:

 #!/usr/local/bin/python from itertools import combinations def find_sum_in_list(numbers, target): results = [] for x in range(len(numbers)): results.extend( [ combo for combo in combinations(numbers ,x) if sum(combo) == target ] ) print results if __name__ == "__main__": find_sum_in_list([3,9,8,4,5,7,10], 15) 

आउटपुट: [(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]

जावा समाधान का स्विफ्ट 3 रूपांतरण: (जेरेमी टोम्प्सन द्वारा)

 protocol _IntType { } extension Int: _IntType {} extension Array where Element: _IntType { func subsets(to: Int) -> [[Element]]? { func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) { var sum: Int = 0 for x in partial { sum += x as! Int } if sum == target { solution.append(partial) } guard sum < target else { return } for i in stride(from: 0, to: numbers.count, by: 1) { var remaining = [Element]() for j in stride(from: i + 1, to: numbers.count, by: 1) { remaining.append(numbers[j]) } var partial_rec = [Element](partial) partial_rec.append(numbers[i]) sum_up_recursive(remaining, target, partial_rec, &solution) } } var solutions = [[Element]]() sum_up_recursive(self, to, [Element](), &solutions) return solutions.count > 0 ? solutions : nil } } 

उपयोग:

 let numbers = [3, 9, 8, 4, 5, 7, 10] if let solution = numbers.subsets(to: 15) { print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]] } else { print("not possible") } 

इसका उपयोग सभी उत्तरों को भी प्रिंट करने के लिए किया जा सकता है

 public void recur(int[] a, int n, int sum, int[] ans, int ind) { if (n < 0 && sum != 0) return; if (n < 0 && sum == 0) { print(ans, ind); return; } if (sum >= a[n]) { ans[ind] = a[n]; recur(a, n - 1, sum - a[n], ans, ind + 1); } recur(a, n - 1, sum, ans, ind); } public void print(int[] a, int n) { for (int i = 0; i < n; i++) System.out.print(a[i] + " "); System.out.println(); } 

समय जटिलता घातीय है 2 का आदेश ^ एन

मैं एक स्केल असाइनमेंट के लिए कुछ इसी तरह कर रहा था। मेरे समाधान को यहां पोस्ट करने का विचार:

  def countChange(money: Int, coins: List[Int]): Int = { def getCount(money: Int, remainingCoins: List[Int]): Int = { if(money == 0 ) 1 else if(money < 0 || remainingCoins.isEmpty) 0 else getCount(money, remainingCoins.tail) + getCount(money - remainingCoins.head, remainingCoins) } if(money == 0 || coins.isEmpty) 0 else getCount(money, coins) } 

बेहतर आउटपुट स्वरूपण और सी ++ 11 सुविधाओं के साथ यह एक बेहतर संस्करण है:

 void subset_sum_rec(std::vector<int> & nums, const int & target, std::vector<int> & partialNums) { int currentSum = std::accumulate(partialNums.begin(), partialNums.end(), 0); if (currentSum > target) return; if (currentSum == target) { std::cout << "sum(["; for (auto it = partialNums.begin(); it != std::prev(partialNums.end()); ++it) cout << *it << ","; cout << *std::prev(partialNums.end()); std::cout << "])=" << target << std::endl; } for (auto it = nums.begin(); it != nums.end(); ++it) { std::vector<int> remaining; for (auto it2 = std::next(it); it2 != nums.end(); ++it2) remaining.push_back(*it2); std::vector<int> partial = partialNums; partial.push_back(*it); subset_sum_rec(remaining, target, partial); } } 

यहां आर में एक समाधान है

 subset_sum = function(numbers,target,partial=0){ if(any(is.na(partial))) return() s = sum(partial) if(s == target) print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target)) if(s > target) return() for( i in seq_along(numbers)){ n = numbers[i] remaining = numbers[(i+1):length(numbers)] subset_sum(remaining,target,c(partial,n)) } } 

एक्सेल VBA संस्करण नीचे। मुझे इसे VBA में कार्यान्वित करने की जरूरत है (मेरी वरीयता नहीं, मुझे न्याय न करें!), और दृष्टिकोण के लिए इस पृष्ठ पर दिए गए उत्तरों का इस्तेमाल किया। मैं दूसरों को भी एक VBA संस्करण की आवश्यकता के मामले में अपलोड कर रहा हूँ

 Option Explicit Public Sub SumTarget() Dim numbers(0 To 6) As Long Dim target As Long target = 15 numbers(0) = 3: numbers(1) = 9: numbers(2) = 8: numbers(3) = 4: numbers(4) = 5 numbers(5) = 7: numbers(6) = 10 Call SumUpTarget(numbers, target) End Sub Public Sub SumUpTarget(numbers() As Long, target As Long) Dim part() As Long Call SumUpRecursive(numbers, target, part) End Sub Private Sub SumUpRecursive(numbers() As Long, target As Long, part() As Long) Dim s As Long, i As Long, j As Long, num As Long Dim remaining() As Long, partRec() As Long s = SumArray(part) If s = target Then Debug.Print "SUM ( " & ArrayToString(part) & " ) = " & target If s >= target Then Exit Sub If (Not Not numbers) <> 0 Then For i = 0 To UBound(numbers) Erase remaining() num = numbers(i) For j = i + 1 To UBound(numbers) AddToArray remaining, numbers(j) Next j Erase partRec() CopyArray partRec, part AddToArray partRec, num SumUpRecursive remaining, target, partRec Next i End If End Sub Private Function ArrayToString(x() As Long) As String Dim n As Long, result As String result = "{" & x(n) For n = LBound(x) + 1 To UBound(x) result = result & "," & x(n) Next n result = result & "}" ArrayToString = result End Function Private Function SumArray(x() As Long) As Long Dim n As Long SumArray = 0 If (Not Not x) <> 0 Then For n = LBound(x) To UBound(x) SumArray = SumArray + x(n) Next n End If End Function Private Sub AddToArray(arr() As Long, x As Long) If (Not Not arr) <> 0 Then ReDim Preserve arr(0 To UBound(arr) + 1) Else ReDim Preserve arr(0 To 0) End If arr(UBound(arr)) = x End Sub Private Sub CopyArray(destination() As Long, source() As Long) Dim n As Long If (Not Not source) <> 0 Then For n = 0 To UBound(source) AddToArray destination, source(n) Next n End If End Sub 

आउटपुट (तत्काल विंडो में लिखा हुआ) होना चाहिए:

 SUM ( {3,8,4} ) = 15 SUM ( {3,5,7} ) = 15 SUM ( {8,7} ) = 15 SUM ( {5,10} ) = 15 

मैंने सी # नमूना को उद्देश्य-सी पर रख दिया और इसे प्रतिक्रियाओं में नहीं देखा:

 //Usage NSMutableArray* numberList = [[NSMutableArray alloc] init]; NSMutableArray* partial = [[NSMutableArray alloc] init]; int target = 16; for( int i = 1; i<target; i++ ) { [numberList addObject:@(i)]; } [self findSums:numberList target:target part:partial]; //******************************************************************* // Finds combinations of numbers that add up to target recursively //******************************************************************* -(void)findSums:(NSMutableArray*)numbers target:(int)target part:(NSMutableArray*)partial { int s = 0; for (NSNumber* x in partial) { s += [x intValue]; } if (s == target) { NSLog(@"Sum[%@]", partial); } if (s >= target) { return; } for (int i = 0;i < [numbers count];i++ ) { int n = [numbers[i] intValue]; NSMutableArray* remaining = [[NSMutableArray alloc] init]; for (int j = i + 1; j < [numbers count];j++) { [remaining addObject:@([numbers[j] intValue])]; } NSMutableArray* partRec = [[NSMutableArray alloc] initWithArray:partial]; [partRec addObject:@(n)]; [self findSums:remaining target:target part:partRec]; } } 

@ किथबेलर का जवाब थोड़ा बदल गया चर नाम और कुछ टिप्पणियों के साथ।

  public static void Main(string[] args) { List<int> input = new List<int>() { 3, 9, 8, 4, 5, 7, 10 }; int targetSum = 15; SumUp(input, targetSum); } public static void SumUp(List<int> input, int targetSum) { SumUpRecursive(input, targetSum, new List<int>()); } private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> listToSum) { // Sum up partial int sum = 0; foreach (int x in listToSum) sum += x; //Check sum matched if (sum == targetSum) Console.WriteLine("sum(" + string.Join(",", listToSum.ToArray()) + ")=" + targetSum); //Check sum passed if (sum >= targetSum) return; //Iterate each input character for (int i = 0; i < remaining.Count; i++) { //Build list of remaining items to iterate List<int> newRemaining = new List<int>(); for (int j = i + 1; j < remaining.Count; j++) newRemaining.Add(remaining[j]); //Update partial list List<int> newListToSum = new List<int>(listToSum); int currentItem = remaining[i]; newListToSum.Add(currentItem); SumUpRecursive(newRemaining, targetSum, newListToSum); } }' 

PHP संस्करण , जैसा कीथ बेलर के सी # संस्करण से प्रेरित है।

बाला का PHP संस्करण मेरे लिए काम नहीं करता, क्योंकि मुझे समूह संख्याओं की आवश्यकता नहीं थी। मैं एक लक्ष्य मूल्य के साथ एक सरल कार्यान्वयन चाहता था, और संख्याओं का एक पूल। यह फ़ंक्शन किसी भी डुप्लिकेट प्रविष्टियों को छेड़छाड़ करेगा।

 /** * Calculates a subset sum: finds out which combinations of numbers * from the numbers array can be added together to come to the target * number. * * Returns an indexed array with arrays of number combinations. * * Example: * * <pre> * $matches = subset_sum(array(5,10,7,3,20), 25); * </pre> * * Returns: * * <pre> * Array * ( * [0] => Array * ( * [0] => 3 * [1] => 5 * [2] => 7 * [3] => 10 * ) * [1] => Array * ( * [0] => 5 * [1] => 20 * ) * ) * </pre> * * @param number[] $numbers * @param number $target * @param array $part * @return array[number[]] */ function subset_sum($numbers, $target, $part=null) { // we assume that an empty $part variable means this // is the top level call. $toplevel = false; if($part === null) { $toplevel = true; $part = array(); } $s = 0; foreach($part as $x) { $s = $s + $x; } // we have found a match! if($s == $target) { sort($part); // ensure the numbers are always sorted return array(implode('|', $part)); } // gone too far, break off if($s >= $target) { return null; } $matches = array(); $totalNumbers = count($numbers); for($i=0; $i < $totalNumbers; $i++) { $remaining = array(); $n = $numbers[$i]; for($j = $i+1; $j < $totalNumbers; $j++) { $remaining[] = $numbers[$j]; } $part_rec = $part; $part_rec[] = $n; $result = subset_sum($remaining, $target, $part_rec); if($result) { $matches = array_merge($matches, $result); } } if(!$toplevel) { return $matches; } // this is the top level function call: we have to // prepare the final result value by stripping any // duplicate results. $matches = array_unique($matches); $result = array(); foreach($matches as $entry) { $result[] = explode('|', $entry); } return $result; } 

एक उत्तर के रूप में अनुशंसित:

एएस2015 जेनरेटर का उपयोग कर एक समाधान है:

 function* subsetSum(numbers, target, partial = [], partialSum = 0) { if(partialSum === target) yield partial if(partialSum >= target) return for(let i = 0; i < numbers.length; i++){ const remaining = numbers.slice(i + 1) , n = numbers[i] yield* subsetSum(remaining, target, [...partial, n], partialSum + n) } } 

जनरेटर का उपयोग वास्तव में बहुत उपयोगी हो सकता है क्योंकि यह आपको एक वैध सबसेट खोजें पाने के तुरंत बाद स्क्रिप्ट निष्पादन को रोक देता है। यह जनरेटर के बिना समाधान (यानी कमी राज्य) के विपरीत है, जो numbers प्रत्येक एक सबसेट के माध्यम से फिर से चलना पड़ता है