如何最大化选择组合分组以完全使用源数组的所有数值

需求说明 #

实现函数maximizeGroups，接收两个参数：

• 候选组合数组groups
• 源数值数组source
  要求从groups中选出尽可能多的互不冲突的组合，满足组合包含的所有元素刚好耗尽source的全部数值，每个数值仅能使用一次。

示例参考 #

function maximizeGroups(groups, source) {}

const groups = [[10], [1, 3, 6], [1, 9], [3, 7], [4, 6]];
const source = [6, 1, 3, 10, 4, 7, 9]

console.log(maximizeGroups(groups, source)) 
// 预期结果 [[10], [1,9], [3,7], [4,6]] （组合内部元素顺序、组合排列顺序不影响，只要组合匹配、数量最多即可）

示例中[1, 3, 6]被舍弃，因为如果使用该组合，剩余的数值无法凑出其他有效组合，最终选中的组合总数会更少。

原有实现的问题 #

你当前的代码存在以下缺陷：

• 仅支持删除1个组合的场景，若需要删除多个组合才能满足条件时会直接返回null
• 没有校验选中组合是否存在元素重叠，可能返回包含重复使用数值的非法结果
• 没有优先保证选中组合的数量最多，只要找到总元素匹配的组合列表就直接返回，不一定满足数量最大化的要求

正确实现方案 #

我们采用回溯+剪枝的思路，优先尝试长度更短的组合（短组合更容易凑出更多数量），遍历所有可能的组合选择方案，记录数量最多的合法结果：

function maximizeGroups(groups, source) {
  // 统计source中每个数值的出现次数
  const sourceCount = {}
  source.forEach(num => {
    sourceCount[num] = (sourceCount[num] || 0) + 1
  })
  // 按组合长度升序排序，优先选短组合，更容易得到最多数量的结果，也方便后续剪枝
  const sortedGroups = [...groups].sort((a, b) => a.length - b.length)
  let maxResult = []

  // 回溯函数
  function backtrack(start, currentSelected, remainingCount) {
    // 若当前选中组合数量超过已记录的最大结果，且数值刚好耗尽，更新最大结果
    if (currentSelected.length > maxResult.length) {
      const isAllUsed = Object.values(remainingCount).every(cnt => cnt === 0)
      if (isAllUsed) maxResult = [...currentSelected]
    }

    // 剪枝：剩余可选组合就算全选也达不到当前最大数量，直接终止当前分支
    if (currentSelected.length + (sortedGroups.length - start) <= maxResult.length) return

    for (let i = start; i < sortedGroups.length; i++) {
      const group = sortedGroups[i]
      // 校验当前组合元素剩余量是否足够
      const canSelect = group.every(num => remainingCount[num] > 0)
      if (!canSelect) continue

      // 校验组合本身是否有重复元素超出source存量
      const groupCount = {}
      let groupValid = true
      for (const num of group) {
        groupCount[num] = (groupCount[num] || 0) + 1
        if (groupCount[num] > sourceCount[num]) {
          groupValid = false
          break
        }
      }
      if (!groupValid) continue

      // 更新剩余计数，递归搜索下一个组合
      const newRemaining = {...remainingCount}
      group.forEach(num => newRemaining[num]--)
      currentSelected.push(group)
      backtrack(i + 1, currentSelected, newRemaining)
      // 回溯回退状态
      currentSelected.pop()
    }
  }

  backtrack(0, [], sourceCount)
  return maxResult.length ? maxResult : null
}

// 测试效果
const groups = [[10], [1, 3, 6], [1, 9], [3, 7], [4, 6]];
const source = [6, 1, 3, 10, 4, 7, 9];
console.log(maximizeGroups(groups, source))
// 输出：[ [10], [1,9], [3,7], [4,6] ] 与预期匹配

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