जावास्क्रिप्ट का उपयोग करके संयोजन योग समस्या

मान लीजिए कि हमें उम्मीदवार संख्या का एक सेट (डुप्लिकेट के बिना) और एक लक्ष्य संख्या (लक्ष्य) दिया गया है।

हमें एक ऐसा फ़ंक्शन लिखना है जो उम्मीदवारों में सभी अद्वितीय संयोजन ढूंढता है जहां उम्मीदवार संख्या लक्ष्य के बराबर होती है।

वही दोहराई गई संख्या उम्मीदवारों से असीमित बार चुनी जा सकती है।

नोट -

• सभी संख्याएं (लक्ष्य सहित) धनात्मक पूर्णांक होंगी।

• समाधान सेट में डुप्लिकेट संयोजन नहीं होने चाहिए।

उदाहरण के लिए -

यदि इनपुट हैं -

candidates = [2,3,6,7], target = 7,

इसका समाधान हो सकता है -

[
   [7],
   [2,2,3]
];

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

उदाहरण

निम्नलिखित कोड है -

const recursiveSum = (
   candidates,
   remainingSum,
   finalCombinations = [],
   currentCombination = [],
   startFrom = 0,
) => {
   if (remainingSum < 0) {
      return finalCombinations;
   }
   if (remainingSum === 0) {
      finalCombinations.push(currentCombination.slice());
      return finalCombinations;
   }
   for (let candidateIndex = startFrom; candidateIndex < candidates.length; candidateIndex += 1) {
      const currentCandidate = candidates[candidateIndex];
      currentCombination.push(currentCandidate);
      recursiveSum(
         candidates,
         remainingSum - currentCandidate,
         finalCombinations,
         currentCombination,
         candidateIndex,
      );
      currentCombination.pop();
   }
   return finalCombinations;
}
const combinationSum = (candidates, target) => recursiveSum(candidates, target);
console.log(combinationSum([2, 3, 6, 7], 7));

आउटपुट

कंसोल पर आउटपुट निम्नलिखित है -

[ [ 2, 2, 3 ], [ 7 ] ]