将集合划分为和差最小的两个子集并返回，非NP-hard解法及双列堆叠应用

首先明确：该问题本质是经典的集合分区问题，严格来说不存在多项式时间的精确最优解法，属于NP-hard问题。如果你可以接受近似最优解，或者元素总规模不大，有两种完全不需要枚举所有子集的实用方案可选。

现有代码问题 #

你当前用的是基础的「大元素优先放入较矮列」的贪心逻辑，且判断条件存在冗余：sum(rs) + nextItem.size > sum(ls) + nextItem.size 等价于直接比较sum(rs) > sum(ls)，这个逻辑在部分测试用例下会得到非最优结果，也就是你遇到的inputNotWorking的问题。

方案1：Karmarkar-Karp 最大差分贪心算法 #

时间复杂度仅为O(n log n)，不需要枚举，对于绝大多数普通业务场景的近似精度远高于基础贪心，大部分场景下可以得到精确最优解：

// 输入按大小升序排列即可
function karmarkarKarpPartition(items) {
    // 维护堆，每个元素结构为[当前堆总大小, 堆内元素列表]
    let heap = items.map(item => [item.size, [item]]);
    // 按堆大小降序排序，模拟大顶堆
    while (heap.length > 1) {
        heap.sort((a, b) => b[0] - a[0]);
        // 取出最大的两个堆
        const first = heap.shift();
        const second = heap.shift();
        // 合并两个堆，差值作为新堆的大小，元素合并到较小的堆一侧
        const mergedSize = Math.abs(first[0] - second[0]);
        const mergedItems = first[0] >= second[0] 
            ? first[1].concat(second[1].map(i => ({...i, __side: 'right'})))
            : second[1].concat(first[1].map(i => ({...i, __side: 'right'})));
        heap.push([mergedSize, mergedItems]);
    }
    // 拆分左右子集
    const left = heap[0][1].filter(i => !i.__side);
    const right = heap[0][1].filter(i => i.__side).map(i => {
        const {__side, ...rest} = i;
        return rest;
    });
    const leftSum = sumSizes(left);
    const rightSum = sumSizes(right);
    return {
        left,
        right,
        maxHeight: Math.max(leftSum, rightSum)
    }
}

function sumSizes(itemSizeArray) {
  return itemSizeArray.reduce((prev, curr) => prev + curr.size, 0);
}

// 测试用例
let inputWorking = [
  {item: 'a', size: 5},
  {item: 'b', size: 6},
  {item: 'c', size: 7},
  {item: 'd', size: 8},
];
let inputNotWorking = [
  {item: 'a', size: 14},
  {item: 'b', size: 14},
  {item: 'c', size: 20},
  {item: 'd', size: 20},
  {item: 'e', size: 21},
];
console.log(karmarkarKarpPartition(inputWorking));
console.log(karmarkarKarpPartition(inputNotWorking)); // 输出maxHeight为48，符合预期

方案2：动态规划精确解法 #

如果你必须要100%的精确最优解，且所有元素的总高度S不超过10000的量级，可以用动态规划方案，时间复杂度为O(nS)，远优于枚举所有子集的O(2^n)，还可以回溯得到具体的子集划分：

function exactPartition(items) {
    const total = sumSizes(items);
    const target = Math.floor(total / 2);
    const n = items.length;
    // dp[i][j] 表示前i个元素能不能凑出和为j
    const dp = Array.from({length: n+1}, () => Array(target + 1).fill(false));
    dp[0][0] = true;
    for (let i = 1; i <= n; i++) {
        const size = items[i-1].size;
        for (let j = 0; j <= target; j++) {
            dp[i][j] = dp[i-1][j] || (j >= size ? dp[i-1][j - size] : false);
        }
    }
    // 找到最大的可达j
    let maxJ = 0;
    for (let j = target; j >=0; j--) {
        if (dp[n][j]) {
            maxJ = j;
            break;
        }
    }
    // 回溯得到选中的元素
    const left = [];
    let j = maxJ;
    for (let i = n; i > 0; i--) {
        const size = items[i-1].size;
        if (j >= size && dp[i-1][j - size]) {
            left.push(items[i-1]);
            j -= size;
        }
    }
    const right = items.filter(item => !left.includes(item));
    return {
        left,
        right,
        maxHeight: Math.max(sumSizes(left), sumSizes(right))
    }
}

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