Tìm n mảng con có tổng 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à một số nguyên làm đối số thứ hai.

Hàm nên kiểm tra xem có thể tạo ra n (đối số thứ hai) mảng con từ mảng gốc sao cho tất cả các mảng con có tổng bằng nhau hay không.

Ví dụ:

Nếu đầu vào là:

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

Đầu ra nên là true vì các mảng con là: [5], [1, 4], [2, 3], [2, 3] tất cả có tổng bằng 5.

Ví dụ

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

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));

Kết quả

Đầu ra trên console:

true

Giải thích: Đây là bài toán "Partition to K Equal Sum Subsets" (LeetCode 691). Backtracking với pruning: tổng phải chia hết cho k, tìm từng subset đạt target. Độ phức tạp mũ, phù hợp mảng nhỏ.