如何实现JS/TS函数：将数组等长分割为N组且组和差异最小

这个问题的核心是同时满足分组等长、组和差异最小，普通数组分区算法只关注组和不限制长度，因此不适用。下面是基于贪心策略的JS/TS实现，能高效给出近似最优解（多数场景下即为最优解）：

实现思路 #

1. 计算基础参数：每个分组的固定长度groupSize = 原数组长度 / N，数组总总和totalSum，以及理想组和targetSum = totalSum / N。
2. 将原数组降序排序，优先处理大元素，避免大元素集中在同一组导致和差过大。
3. 初始化N个分组，每个分组维护当前的元素列表和元素和。
4. 遍历排序后的每个元素，将其放入当前和最小且元素数量未达groupSize的分组中，确保每次用大元素填补最“缺”的组，平衡各组和。

TS代码实现 #

function splitIntoEqualLengthGroups(arr: number[], groupCount: number): number[][] {
    const groupSize = arr.length / groupCount;
    if (!Number.isInteger(groupSize)) {
        throw new Error("数组长度必须能被分组数整除");
    }

    // 降序排序数组
    const sortedArr = [...arr].sort((a, b) => b - a);
    // 初始化分组：每个分组包含元素列表和当前和
    const groups: { elements: number[], sum: number }[] = Array.from({ length: groupCount }, () => ({
        elements: [],
        sum: 0
    }));

    for (const num of sortedArr) {
        // 找到当前和最小且元素数量未达上限的分组
        const targetGroup = groups.reduce((prev, curr) => {
            if (curr.elements.length >= groupSize) return prev;
            if (prev.elements.length >= groupSize) return curr;
            return curr.sum < prev.sum ? curr : prev;
        });

        targetGroup.elements.push(num);
        targetGroup.sum += num;
    }

    // 只返回元素列表
    return groups.map(g => g.elements);
}

// 测试示例
const baseArray = [5,4,3,2,2,1];
const numberOfGroupsNeeded = 2;
const result = splitIntoEqualLengthGroups(baseArray, numberOfGroupsNeeded);
console.log(result); // 输出类似 [[4,3,2], [5,2,1]] 或 [[5,2,1], [4,3,2]]

结果说明 #

对于示例输入，排序后的数组是[5,4,3,2,2,1]，分组过程如下：

• 5放入第一个组，组1：[5]，和5
• 4放入当前和最小的组2，组2：[4]，和4
• 3放入组2，组2：[4,3]，和7
• 2放入组1，组1：[5,2]，和7
• 2放入任意一个未满的组（此处放入组2），组2：[4,3,2]，和9
• 1放入组1，组1：[5,2,1]，和8

最终两组和分别为9和8，差异为1，是理论最小差异（总总和17无法分成两个相等的整数和），符合期望输出。

关于精确最优解 #

如果需要绝对最优解（极端场景下贪心可能略逊），可以采用回溯算法枚举所有可能的分组，但时间复杂度会指数级上升，仅适合小数据量场景。对于大多数业务场景，上述贪心解法的效率和结果已经足够。

内容的提问来源于stack exchange，提问作者BitState