目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

给定一个数组nums，可以将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，最大的平分组个数。

输入描述

第一行输入 m
接着输入m个数，表示此数组
数据范围:1<=M<=50, 1<=nums[i]<=50

输出描述

最大的平分组数个数

用例

题目解析

本题和

华为机试 - 叠积木_伏城之外的博客-CSDN博客_叠积木 算法

华为机试 - 等和子数组最小和_伏城之外的博客-CSDN博客

属于类似，解题步骤基本相同。

题解请看叠积木。

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
rl.on("line", (line) => {lines.push(line);if (lines.length === 2) {const m = lines[0] - 0;const arr = lines[1].split(" ").map(Number);console.log(getResutlt(m, arr));lines.length = 0;}
});function getResutlt(m, arr) {const sum = arr.sort((a, b) => b - a).reduce((p, c) => p + c);let maxCount = m;while (maxCount >= 1) {if (canPartition(arr, sum, maxCount)) {return maxCount;} else {maxCount--;}}
}function canPartition(arr, sum, maxCount) {if (sum % maxCount) return false;const subSum = sum / maxCount;if (subSum < arr[0]) return false;while (arr[0] === subSum) {arr.shift();maxCount--;}const buckets = new Array(maxCount).fill(0);return partition(0, arr, subSum, buckets);
}function partition(start, arr, subSum, buckets) {if (start === arr.length) return true;const select = arr[start];for (let i = 0; i < buckets.length; i++) {if (i > 0 && buckets[i] === buckets[i - 1]) continue;if (buckets[i] + select <= subSum) {buckets[i] += select;if (partition(start + 1, arr, subSum, buckets)) return true;buckets[i] -= select;}}return false;
}