Vấn đề
Chúng ta cần viết một hàm JavaScript nhận vào một mảng số arr làm đối số đầu tiên và một số num làm đối số thứ hai.
Hàm phải xác định xem có cách nào phân phối các phần tử của mảng arr thành num nhóm sao cho tất cả các nhóm có tổng bằng nhau hay không. Nếu tồn tại cách như vậy, hàm trả về true, ngược lại trả về false.
Ví dụ:
Nếu mảng đầu vào và số là:
const arr = [4, 6, 3, 3, 7, 4, 1]; const num = 4;
Kết quả đầu ra nên là:
const output = true;
bốn nhóm là: [7], [1, 6], [4, 3], [4, 3]
Ví dụ
Mã thực hiện như sau:
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));
Các bước trong giải pháp:
Bước 1. Nếu tổng không chia hết cho num hoặc có số lớn hơn sum/num, trả về false.
Bước 2. Sử dụng HashSet để theo dõi các số đã dùng.
Bước 3. Bắt đầu tìm các phân vùng con.
Nếu tất cả các số đã được dùng, hoàn thành.
Nếu tổng tập con quá lớn, dừng tìm kiếm.
Nếu tìm thấy một tập con, tiếp tục tìm kiếm cho đến khi dùng hết các số.
Cuối cùng, thử mọi số chưa dùng.
Kết quả
Kết quả in ra console:
true