ปัญหา Combination Sum ใน JavaScript

ปัญหา Combination Sum

กำหนดชุดตัวเลขหล보 (Candidates) ไม่ซ้ำกัน และตัวเลขเป้าหมาย (Target) หา ทุกชุดการรวม (Combinations) ที่ผลรวมเท่ากับ Target โดย ตัวเลขแต่ละตัวใช้ได้ไม่จำกัดครั้ง

ตัวอย่าง

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

คำตอบ:

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

โค้ดตัวอย่าง (Backtracking)

const recursiveSum = (
  candidates,
  remainingSum,
  finalCombinations = [],
  currentCombination = [],
  startFrom = 0
) => {
  // Base cases
  if (remainingSum < 0) return finalCombinations;
  if (remainingSum === 0) {
    finalCombinations.push(currentCombination.slice());
    return finalCombinations;
  }
  
  // ลองทุกตัวเลือกจาก startFrom
  for (let candidateIndex = startFrom; candidateIndex < candidates.length; candidateIndex++) {
    const currentCandidate = candidates[candidateIndex];
    currentCombination.push(currentCandidate);
    
    // Recursive: ใช้ตัวเลขเดิมได้อีก (candidateIndex ไม่ +1)
    recursiveSum(
      candidates,
      remainingSum - currentCandidate,
      finalCombinations,
      currentCombination,
      candidateIndex
    );
    
    currentCombination.pop(); // Backtrack
  }
  return finalCombinations;
};

const combinationSum = (candidates, target) => 
  recursiveSum(candidates, target);

console.log(combinationSum([2, 3, 6, 7], 7));

ผลลัพธ์

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

คำอธิบาย Backtracking

1. Choose: เลือกตัวเลขจาก candidates เริ่มจาก startFrom
2. Explore: เรียก recursive ด้วย remainingSum ลดลง
3. Un-choose: pop() ออกเมื่อย้อนกลับ (Backtrack)
4. startFrom ป้องกัน duplicate combinations (เช่น [2,3] และ [3,2] นับเป็นเดียวกัน)

ความซับซ้อน

• Time: O(N^(T/M)) โดย N=จำนวน candidates, T=target, M=ค่าต่ำสุดใน candidates
• Space: O(T/M) สำหรับ recursion stack
• เป็น NP-Hard problem ไม่มี polynomial-time algorithm

เวอร์ชันสั้น (Modern JS)

const combinationSum = (candidates, target) => {
  const result = [];
  const backtrack = (remain, combo, start) => {
    if (remain === 0) return result.push([...combo]);
    if (remain < 0) return;
    for (let i = start; i < candidates.length; i++) {
      combo.push(candidates[i]);
      backtrack(remain - candidates[i], combo, i);
      combo.pop();
    }
  };
  backtrack(target, [], 0);
  return result;
};