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

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลข arr เป็นอาร์กิวเมนต์แรก และตัวเลข num เป็นอาร์กิวเมนต์ที่สอง ฟังก์ชันควรกำหนดว่าสามารถกระจายองค์ประกอบของอาร์เรย์ arr เข้าไปใน num กลุ่มได้หรือไม่ โดยที่ทุกกลุ่มต้องมีผลรวมเท่ากัน หากมีวิธีการใดๆ ที่ทำได้ ให้คืนค่า true มิฉะนั้นคืน false

ตัวอย่าง

const arr = [4, 6, 3, 3, 7, 4, 1]; 
const num = 4;

ผลลัพธ์ควรเป็น true เพราะสามารถแบ่งเป็น 4 กลุ่มได้ดังนี้: [7], [1, 6], [4, 3], [4, 3]

การแก้ปัญหา

const arr = [4, 6, 3, 3, 7, 4, 1]; 
const num = 4; 
const canDivide = (arr = [], num = 1) => { 
  const sum = arr.reduce((acc, num) => acc + num); 
  if (sum % num !== 0 || arr.some(num => num > sum / num)) { 
    return false; 
  } 
  const used = new Set(); 
  return (function find(start, target) { 
    if (used.size === arr.length) { 
      return true; 
    } 
    if (target < 0) { 
      return false; 
    } 
    if (target === 0) { 
      return find(0, sum / num); 
    } 
    for (let i = start; i < arr.length; i++) { 
      if (!used.has(i)) { 
        used.add(i); 
        if (find(i + 1, target - arr[i])) { 
          return true; 
        } 
        used.delete(i); 
      } 
    } 
    return false; 
  })(0, sum / num); 
}; 
console.log(canDivide(arr, num));

ขั้นตอนการทำงาน

• ขั้นตอน 1: หากผลรวมทั้งหมดหารด้วย num ไม่ลงตัว หรือมีตัวเลขใดมากกว่า sum/num ให้คืน false ทันที
• ขั้นตอน 2: ใช้ HashSet เพื่อติดตามดัชนีที่ใช้แล้ว
• ขั้นตอน 3: เริ่มค้นหาส่วนย่อยแบบเรียกซ้ำ (recursive)
• ถ้าทุกตัวเลขถูกใช้หมดแล้ว แสดงว่าพบวิธีแบ่งที่ถูกต้อง
• ถ้าผลรวมสะสมเกินเป้าหมาย ให้หยุดค้นหาเส้นทางนั้น
• เมื่อพบกลุ่มหนึ่งที่ครบ ให้ต่อไปค้นหากลุ่มถัดไปจนกว่าจะใช้ตัวเลขหมด
• ลองทุกตัวเลขที่ยังไม่ได้ใช้

ผลลัพธ์

true