การตรวจสอบการแบ่งอาร์เรย์เป็น n สับอาร์เรย์ที่มีผลรวมเท่ากันใน JavaScript

บทความนี้สาธิตอัลกอริทึมแบ่งอาร์เรย์ (Partition to K Equal Sum Subsets) ตรวจสอบว่าสามารถแบ่งอาร์เรย์เป็น n สับอาร์เรย์ที่มีผลรวมเท่ากันได้หรือไม่

ตัวอย่าง

const arr = [4, 3, 2, 3, 5, 2, 1];
const num = 4;
// สับอาร์เรย์: [5], [1,4], [2,3], [2,3] ผลรวมแต่ละชุด = 5

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

const arr = [4, 3, 2, 3, 5, 2, 1];
const num = 4;

const canFormSubarray = (arr = [], num) => {
  const total = arr.reduce((sum, num) => sum + num, 0);
  if (total % num !== 0) {
    return false;
  }
  const target = total / num;
  const visited = new Array(arr.length).fill(false);

  const canPartition = (start, numberOfSubsets, currentSum) => {
    if (numberOfSubsets === 1) {
      return true;
    }
    if (currentSum === target) {
      return canPartition(0, numberOfSubsets - 1, 0);
    }
    for (let i = start; i < arr.length; i++) {
      if (!visited[i]) {
        visited[i] = true;
        if (canPartition(i + 1, numberOfSubsets, currentSum + arr[i])) {
          return true;
        }
        visited[i] = false;
      }
    }
    return false;
  };

  return canPartition(0, num, 0);
};

console.log(canFormSubarray(arr, num));

ผลลัพธ์

true

คำอธิบาย

ใช้ backtracking + pruning: ตรวจสอบผลรวมทั้งหมดหาร num ลงตัวก่อน คำนวณ target sum ต่อชุด

ฟังก์ชัน canPartition พยายามสร้างชุดที่มีผลรวม = target โดยใช้ visited array ป้องกันการใช้ซ้ำ เมื่อสร้างชุดเสร็จ 1 ชุด จะเรียก recursive หาชุดถัดไป

Complexity: Exponential ใน worst case