อาร์เรย์สามารถแบ่งออกเป็น n พาร์ติชั่นโดยมีผลรวมเท่ากันใน JavaScript

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลข arr เป็นอาร์กิวเมนต์แรกและตัวเลข num เป็นอาร์กิวเมนต์ที่สอง

ฟังก์ชันควรกำหนดว่ามีวิธีการกระจายองค์ประกอบของอาร์เรย์ arr ออกเป็นกลุ่ม num หรือไม่ เพื่อให้ทุกกลุ่มมีผลรวมเท่ากัน หากมีวิธีการดังกล่าว ฟังก์ชันของเราควรคืนค่า true ไม่เช่นนั้นจะคืนค่าเท็จ

ตัวอย่างเช่น −

หากอาร์เรย์อินพุตและตัวเลขเป็น −

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

จากนั้นผลลัพธ์ควรเป็น −

const output = true;

เพราะสี่กลุ่มคือ:[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 เราจะคืนค่าเท็จ

• ขั้นตอนที่ 2 เราใช้ HashSet เพื่อติดตามตัวเลขที่ใช้

• ขั้นตอนที่ 3 เราเริ่มค้นหาพาร์ติชั่นย่อย

• ถ้าใช้ครบทุกเบอร์ก็จบครับ

• หากผลรวมย่อยมากเกินไป เราก็หยุดค้นหา

• หากเราพบชุดย่อยหนึ่งชุด เราจะทำการค้นหาต่อไปจนกว่าเราจะใช้ตัวเลขทั้งหมด

• และสุดท้าย เราลองทุกหมายเลขที่ไม่ได้ใช้

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

true