JavaScript 中可以将数组分成 n 个等和的分区吗

我们需要编写一个 JavaScript 函数，它接受一个数字数组 arr 作为第一个参数，一个数字 num 作为第二个参数。

该函数应确定是否存在将数组 arr 的元素分布到 num 个组中的方法，以使所有组的总和相等。如果存在任何这样的方式，我们的函数应该返回 true，否则返回 false。

例如 -

如果输入数组和数字是 -

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，则返回 false。

• Step2.We使用 HashSet 来跟踪使用过的数字。

• 步骤 3. 我们开始寻找子分区。

• 如果使用所有数字，我们就完成了。

• 如果子集和太大，我们停止搜索。

• 如果我们找到了一个子集，我们继续搜索，直到我们使用所有数字。

• 最后，我们尝试了每个未使用的号码。

输出结果

控制台中的输出将是 -

true