algorithm - 数组的 N 次分区，每个分区的总和相等

Question

给定一个整数数组a，两个数字N和M，返回N组整数a 这样每组总和为 M。

例如，说:

• a = [1,2,3,4,5]
• N = 2
• M = 5

然后算法可以返回 [2, 3], [1, 4] 或 [5], [2, 3] 或其他可能的值。

我可以在这里使用什么算法？

编辑:

我不知道这个问题是 NP 完全的。因此，如果我提供有关我的特定场景的更多详细信息，可能会有所帮助:

所以我正在尝试创建一个“匹配”应用程序。给定球队数量 N 和每个球队的球员数量 M，应用程序监听客户端请求。每个客户端请求都会给出客户端代表的玩家数量。因此，如果我需要 2 个团队，每队 5 个玩家，那么如果有 5 个客户端发送请求，每个请求分别代表 1、2、3、4、5 个玩家，那么我的应用程序应该在客户端 [1, 4] 之间生成匹配 和客户端 [2, 3]。它还可以生成 [1, 4] 和 [5] 之间的匹配；我真的不在乎。

一个含义是任何代表超过 M 或少于 0 玩家的客户端都是无效的。希望这可以简化问题。

Answer 1

这似乎是 subset sum problem 的变体.由于这个问题是 np-complete 的，没有进一步的约束就没有有效的算法。

请注意，已经很难找到原始集合的单个子集，其元素总和为 M。