Chia mảng số thành hai mảng có trung bình bằng nhau trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số nguyên làm đối số đầu tiên và duy nhất.

Hàm cần xác định xem có tồn tại tổ hợp các phần tử của mảng đầu vào mà khi chúng được chia thành hai nhóm (có thể/có thể không có số phần tử bằng nhau), trung bình của cả hai nhóm giống nhau. Nếu tồn tại điều kiện như vậy hàm trả về true, ngược lại false.

Ví dụ:

Nếu mảng đầu vào là:

const arr = [6, 3, 2, 8, 1, 5, 7, 4];

Thì đầu ra nên là:

const output = true;

vì tổ hợp là [8, 1, 5, 4] và [6, 3, 2, 7] vì cả hai nhóm có trung bình 4.5

Ví dụ

Dưới đây là mã nguồn:

const arr = [6, 3, 2, 8, 1, 5, 7, 4]; const canHaveEqualAveragePartition = (arr = []) => {    const sum = arr.reduce((acc, val) => acc + val);    const array = Array(sum+1).fill(false).map(() =>    Array(arr.length+1).fill(false));    array[0][0] = true;    for(let i=0; i < arr.length; ++i){       for(let j=sum - arr[i];j>=0;--j){          for(let k=arr.length-2;k>=0;--k){             if(array[j][k]){                array[j + arr[i]][k+1] = true;                if((j + arr[i]) * (arr.length - k - 1) == (sum - j -arr[i]) * (k + 1)){                   return true;                }             }          }       }    }    return false; }; console.log(canHaveEqualAveragePartition(arr));

Kết quả

Đầu ra trên console:

true

Giải thích: Bài toán "Split Array With Same Average" (LeetCode 805). DP: array[sum][count] = có thể tạo sum với count phần tử không. Kiểm tra điều kiện avg1 = avg2 ⇔ sum1 * (n-k) = sum2 * k. O(n * sum * n) time, có thể tối ưu với meet-in-the-middle cho n lớn.