元素不可复用的组合求和最优分组方案及JavaScript实现

一、最小元素与最大元素配对是否为最优方案 #

首先明确：这类分组问题的最优目标通常是分组数量最少。在这个前提下，排序后优先将最小元素与最大元素配对（必要时补充次小元素凑够数量和目标值）的贪心策略，在绝大多数场景下是高效且接近最优的，但并非绝对适用于所有极端情况。

以题目中的示例来看：
排序后的数组为[5,10,12,15,21,22,25,50]，目标值30，每组最多3个元素。用该策略得到的分组[5,25]、[10,22]、[12,15,21]、[50]，分组数量为4，已是最少可能的结果。

极端反例场景（极少出现）：
假设数组为[1, 2, 27, 29]，目标值30，每组最多2个元素。用最小配最大策略：1+29=30（达标），2+27=29（不达标），此时只能将2和27分别单独分组，但单个27未达标，这说明该数组本身无法满足分组条件。若调整X为3，则策略依然有效：1+2+27=30，29单独分组，共2组，是最优结果。

总结：该贪心策略是处理此类问题的首选高效方案，在输入数组能满足分组条件的前提下，基本能得到最优（分组数最少）的结果。

二、JavaScript实现方案 #

以下是基于上述贪心策略的代码实现，包含完整的边界处理：

function groupElements(arr, target, maxGroupSize) {
    // 复制数组并升序排序，避免修改原数组
    const sortedArr = [...arr].sort((a, b) => a - b);
    const groups = [];
    let left = 0;
    let right = sortedArr.length - 1;

    while (left <= right) {
        // 单个元素已达标，直接单独分组
        if (sortedArr[right] >= target) {
            groups.push([sortedArr[right]]);
            right--;
            continue;
        }

        // 尝试从左指针取元素，和右指针元素组合
        let currentSum = sortedArr[right];
        let currentGroup = [sortedArr[right]];
        let tempLeft = left;

        // 往组内添加左指针元素，直到组满或总和达标
        while (currentGroup.length < maxGroupSize && tempLeft <= right - 1) {
            currentSum += sortedArr[tempLeft];
            currentGroup.unshift(sortedArr[tempLeft]);
            tempLeft++;
            if (currentSum >= target) break;
        }

        // 组合后达标则加入分组，否则说明无法满足条件
        if (currentSum >= target) {
            groups.push(currentGroup);
            left = tempLeft;
            right--;
        } else {
            throw new Error("无法完成分组：剩余元素无法组成符合要求的组");
        }
    }

    return groups;
}

// 测试示例
const exampleArr = [5, 10, 12, 15, 21, 22, 25, 50];
const target = 30;
const maxGroupSize = 3;
console.log(groupElements(exampleArr, target, maxGroupSize));
// 输出：[ [5,25], [10,22], [12,15,21], [50] ]

代码逻辑说明 #

1. 排序预处理：先对数组升序排序，为双指针配对做准备。
2. 双指针遍历：左指针指向当前最小元素，右指针指向当前最大元素。
3. 单独元素判断：若右指针元素本身已达标，直接单独分组。
4. 组合尝试：若右指针元素未达标，从左指针开始依次取元素加入组，直到组内元素数量达到上限maxGroupSize，或总和达标。
5. 分组确认：组合后达标则加入结果集，移动指针继续处理剩余元素；若无法达标则抛出错误（适用于输入无法满足分组条件的场景）。

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