ปัญหาผลรวมโดยใช้ JavaScript

สมมติว่าเราได้รับชุดหมายเลขผู้สมัคร (ไม่ซ้ำกัน) และหมายเลขเป้าหมาย (เป้าหมาย)

เราจำเป็นต้องเขียนฟังก์ชันที่ค้นหาชุดค่าผสมที่ไม่ซ้ำกันทั้งหมดในผู้สมัครโดยที่หมายเลขของผู้สมัครรวมเข้ากับเป้าหมาย

โดยสามารถเลือกหมายเลขซ้ำจากผู้สมัครได้ไม่จำกัดจำนวนครั้ง

หมายเหตุ −

• ตัวเลขทั้งหมด (รวมทั้งเป้าหมาย) จะเป็นจำนวนเต็มบวก

• ชุดโซลูชันต้องไม่มีชุดค่าผสมที่ซ้ำกัน

ตัวอย่าง −

หากอินพุตเป็น −

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

วิธีแก้ไขคือ −

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

เนื่องจากปัญหาคือการได้ผลลัพธ์ที่เป็นไปได้ทั้งหมด ไม่ใช่ผลลัพธ์ที่ดีที่สุดหรือจำนวนผลลัพธ์ เราจึงไม่จำเป็นต้องพิจารณา Dynamic Programming จึงจำเป็นต้องใช้วิธีการย้อนรอยโดยใช้การเรียกซ้ำเพื่อจัดการกับมัน

ตัวอย่าง

ต่อไปนี้เป็นรหัส -

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 ] ]